import sys
import struct

# GIF dimensions
WIDTH = 200
HEIGHT = 200

# Colors (Index 0: White, Index 1: Red)
# Palette: White (255, 255, 255), Red (255, 0, 0)
COLOR_TABLE = bytes([
    255, 255, 255,  # 0: White
    255, 0, 0,      # 1: Red
])
# We need 2 colors, so the Size of Global Color Table field (N)
# satisfies 2^(N+1) = 2, which means N+1=1, so N=0.
GCT_SIZE_N = 0 # Represents 2^(0+1) = 2 colors

# Triangle vertices (simple integer coordinates)
# Top: (100, 20)
# Bottom Left: (20, 180)
# Bottom Right: (180, 180)
v0 = (100, 20)
v1 = (20, 180)
v2 = (180, 180)

# Function to check if a point (x, y) is inside the triangle using edge functions
# Note: This defines the edges in a specific order (e.g., counter-clockwise)
# The sign of the result determines which side of the edge the point is on.
# If all signs are the same (or zero), the point is inside or on the boundary.
def edge_function(p, a, b):
    return (p[0] - a[0]) * (b[1] - a[1]) - (p[1] - a[1]) * (b[0] - a[0])

def is_inside_triangle(x, y):
    p = (x, y)
    # Check signs relative to edges v0->v1, v1->v2, v2->v0
    w0 = edge_function(p, v0, v1)
    w1 = edge_function(p, v1, v2)
    w2 = edge_function(p, v2, v0)
    # Point is inside if all edge functions are non-negative (or all non-positive, depending on winding)
    # For our chosen vertices (CCW order), inside points should yield >= 0
    return w0 >= 0 and w1 >= 0 and w2 >= 0

# Generate pixel data (list of color indices: 0 for white, 1 for red)
pixel_indices = []
for y in range(HEIGHT):
    for x in range(WIDTH):
        if is_inside_triangle(x, y):
            pixel_indices.append(1)  # Red
        else:
            pixel_indices.append(0)  # White

# --- LZW Encoding ---
# We will use a simplified LZW: just output Clear Code, then each pixel index, then EOI code.
# This is valid but not very compressed.

# LZW Minimum Code Size:
# We have 2 colors (0, 1). Need codes for colors + Clear Code + EOI Code.
# Min code size N must satisfy 2^N >= num_colors.
# 2^2 = 4 >= 2. So, N = 2.
LZW_MIN_CODE_SIZE = 2
CLEAR_CODE = 1 << LZW_MIN_CODE_SIZE  # 2^2 = 4
EOI_CODE = CLEAR_CODE + 1            # 4 + 1 = 5

# Bit packing variables
lzw_encoded_bytes = bytearray()
bit_buffer = 0
bits_in_buffer = 0
# Initial code size for *output* stream is LZW_MIN_CODE_SIZE + 1
current_code_size = LZW_MIN_CODE_SIZE + 1 # 3 bits initially

# Helper to write codes to the bit buffer and flush bytes when full
def write_code(code):
    global bit_buffer, bits_in_buffer
    bit_buffer |= (code << bits_in_buffer)
    bits_in_buffer += current_code_size
    while bits_in_buffer >= 8:
        byte = bit_buffer & 0xFF
        lzw_encoded_bytes.append(byte)
        bit_buffer >>= 8
        bits_in_buffer -= 8

# --- Start LZW Stream ---
# 1. Write Clear Code
write_code(CLEAR_CODE)

# 2. Write pixel data indices as codes
for index in pixel_indices:
    write_code(index) # Codes 0 and 1

# 3. Write End of Information Code
write_code(EOI_CODE)

# 4. Flush any remaining bits in the buffer
if bits_in_buffer > 0:
    byte = bit_buffer & 0xFF
    lzw_encoded_bytes.append(byte)

# --- Format LZW data into blocks ---
# Blocks are prefixed with a byte indicating size (1-255), ending with a 0-size block.
image_data_blocks = bytearray()
image_data_blocks.append(LZW_MIN_CODE_SIZE) # Start with the LZW Min Code Size byte

offset = 0
while offset < len(lzw_encoded_bytes):
    chunk_size = min(255, len(lzw_encoded_bytes) - offset)
    image_data_blocks.append(chunk_size) # Size byte
    image_data_blocks.extend(lzw_encoded_bytes[offset : offset + chunk_size]) # Data bytes
    offset += chunk_size

image_data_blocks.append(0) # Zero-length block to end data sub-blocks

# --- Assemble the GIF File ---
gif_bytes = bytearray()

# 1. Header (6 bytes)
gif_bytes.extend(b'GIF89a')

# 2. Logical Screen Descriptor (7 bytes)
packed_lsd_fields = 0b10000000 # Bit 7: GCT Flag=1; Bits 6-4: Color Res=000 (1 bit/color - WRONG, should be 7=111 for 8bit); Bit 3: Sort=0; Bits 2-0: Size of GCT = GCT_SIZE_N
# Corrected Packed Field:
# Bit 7: Global Color Table Flag = 1 (present)
# Bits 6-4: Color Resolution = 111 (8 bits per primary color)
# Bit 3: Sort Flag = 0 (GCT is not sorted)
# Bits 2-0: Size of Global Color Table = GCT_SIZE_N (0 -> table size is 2^(0+1)=2)
# Packed Field = 1 111 0 000 = 0xF0
packed_lsd_fields = 0xF0
background_color_index = 0 # White
pixel_aspect_ratio = 0 # Unspecified

gif_bytes.extend(struct.pack('<HH', WIDTH, HEIGHT)) # Little-endian Width, Height
gif_bytes.append(packed_lsd_fields)
gif_bytes.append(background_color_index)
gif_bytes.append(pixel_aspect_ratio)

# 3. Global Color Table (GCT_SIZE_N implies 2 colors * 3 bytes/color = 6 bytes)
gif_bytes.extend(COLOR_TABLE)

# 4. Image Descriptor (10 bytes)
image_separator = b',' # 0x2C
image_left = 0
image_top = 0
image_width = WIDTH
image_height = HEIGHT
# Packed Field:
# Bit 7: Local Color Table Flag = 0 (no LCT)
# Bit 6: Interlace Flag = 0 (not interlaced)
# Bit 5: Sort Flag = 0
# Bits 4-3: Reserved = 00
# Bits 2-0: Size of LCT = 000 (ignored)
# Packed Field = 00000000 = 0x00
packed_id_fields = 0x00

gif_bytes.extend(image_separator)
gif_bytes.extend(struct.pack('<HHHH', image_left, image_top, image_width, image_height)) # Little-endian positions/dimensions
gif_bytes.append(packed_id_fields)

# 5. Image Data (LZW Min Code Size byte + LZW Data Blocks)
gif_bytes.extend(image_data_blocks)

# 6. Trailer (1 byte)
gif_bytes.extend(b';') # 0x3B

# --- Output to stdout ---
# Write the final byte array to standard output's binary buffer
sys.stdout.buffer.write(gif_bytes)

import sys
import struct

# GIF dimensions
WIDTH = 200
HEIGHT = 200

# Colors (Index 0: White, Index 1: Red)
# Palette: White (255, 255, 255), Red (255, 0, 0)
COLOR_TABLE = bytes([
    255, 255, 255,  # 0: White
    255, 0, 0,      # 1: Red
])
# We need 2 colors, so the Size of Global Color Table field (N)
# satisfies 2^(N+1) = 2, which means N+1=1, so N=0.
GCT_SIZE_N = 0 # Represents 2^(0+1) = 2 colors

# Triangle vertices (simple integer coordinates)
# Top: (100, 20)
# Bottom Left: (20, 180)
# Bottom Right: (180, 180)
v0 = (100, 20)
v1 = (20, 180)
v2 = (180, 180)

# Function to check if a point (x, y) is inside the triangle using edge functions
# Note: This defines the edges in a specific order (e.g., counter-clockwise)
# The sign of the result determines which side of the edge the point is on.
# If all signs are the same (or zero), the point is inside or on the boundary.
def edge_function(p, a, b):
    return (p[0] - a[0]) * (b[1] - a[1]) - (p[1] - a[1]) * (b[0] - a[0])

def is_inside_triangle(x, y):
    p = (x, y)
    # Check signs relative to edges v0->v1, v1->v2, v2->v0
    w0 = edge_function(p, v0, v1)
    w1 = edge_function(p, v1, v2)
    w2 = edge_function(p, v2, v0)
    # Point is inside if all edge functions are non-negative (or all non-positive, depending on winding)
    # For our chosen vertices (CCW order), inside points should yield >= 0
    return w0 >= 0 and w1 >= 0 and w2 >= 0

# Generate pixel data (list of color indices: 0 for white, 1 for red)
pixel_indices = []
for y in range(HEIGHT):
    for x in range(WIDTH):
        if is_inside_triangle(x, y):
            pixel_indices.append(1)  # Red
        else:
            pixel_indices.append(0)  # White

# --- LZW Encoding ---
# We will use a simplified LZW: just output Clear Code, then each pixel index, then EOI code.
# This is valid but not very compressed.

# LZW Minimum Code Size:
# We have 2 colors (0, 1). Need codes for colors + Clear Code + EOI Code.
# Min code size N must satisfy 2^N >= num_colors.
# 2^2 = 4 >= 2. So, N = 2.
LZW_MIN_CODE_SIZE = 2
CLEAR_CODE = 1 << LZW_MIN_CODE_SIZE  # 2^2 = 4
EOI_CODE = CLEAR_CODE + 1            # 4 + 1 = 5

# Bit packing variables
lzw_encoded_bytes = bytearray()
bit_buffer = 0
bits_in_buffer = 0
# Initial code size for *output* stream is LZW_MIN_CODE_SIZE + 1
current_code_size = LZW_MIN_CODE_SIZE + 1 # 3 bits initially

# Helper to write codes to the bit buffer and flush bytes when full
def write_code(code):
    global bit_buffer, bits_in_buffer
    bit_buffer |= (code << bits_in_buffer)
    bits_in_buffer += current_code_size
    while bits_in_buffer >= 8:
        byte = bit_buffer & 0xFF
        lzw_encoded_bytes.append(byte)
        bit_buffer >>= 8
        bits_in_buffer -= 8

# --- Start LZW Stream ---
# 1. Write Clear Code
write_code(CLEAR_CODE)

# 2. Write pixel data indices as codes
for index in pixel_indices:
    write_code(index) # Codes 0 and 1

# 3. Write End of Information Code
write_code(EOI_CODE)

# 4. Flush any remaining bits in the buffer
if bits_in_buffer > 0:
    byte = bit_buffer & 0xFF
    lzw_encoded_bytes.append(byte)

# --- Format LZW data into blocks ---
# Blocks are prefixed with a byte indicating size (1-255), ending with a 0-size block.
image_data_blocks = bytearray()
image_data_blocks.append(LZW_MIN_CODE_SIZE) # Start with the LZW Min Code Size byte

offset = 0
while offset < len(lzw_encoded_bytes):
    chunk_size = min(255, len(lzw_encoded_bytes) - offset)
    image_data_blocks.append(chunk_size) # Size byte
    image_data_blocks.extend(lzw_encoded_bytes[offset : offset + chunk_size]) # Data bytes
    offset += chunk_size

image_data_blocks.append(0) # Zero-length block to end data sub-blocks

# --- Assemble the GIF File ---
gif_bytes = bytearray()

# 1. Header (6 bytes)
gif_bytes.extend(b'GIF89a')

# 2. Logical Screen Descriptor (7 bytes)
packed_lsd_fields = 0b10000000 # Bit 7: GCT Flag=1; Bits 6-4: Color Res=000 (1 bit/color - WRONG, should be 7=111 for 8bit); Bit 3: Sort=0; Bits 2-0: Size of GCT = GCT_SIZE_N
# Corrected Packed Field:
# Bit 7: Global Color Table Flag = 1 (present)
# Bits 6-4: Color Resolution = 111 (8 bits per primary color)
# Bit 3: Sort Flag = 0 (GCT is not sorted)
# Bits 2-0: Size of Global Color Table = GCT_SIZE_N (0 -> table size is 2^(0+1)=2)
# Packed Field = 1 111 0 000 = 0xF0
packed_lsd_fields = 0xF0
background_color_index = 0 # White
pixel_aspect_ratio = 0 # Unspecified

gif_bytes.extend(struct.pack('<HH', WIDTH, HEIGHT)) # Little-endian Width, Height
gif_bytes.append(packed_lsd_fields)
gif_bytes.append(background_color_index)
gif_bytes.append(pixel_aspect_ratio)

# 3. Global Color Table (GCT_SIZE_N implies 2 colors * 3 bytes/color = 6 bytes)
gif_bytes.extend(COLOR_TABLE)

# 4. Image Descriptor (10 bytes)
image_separator = b',' # 0x2C
image_left = 0
image_top = 0
image_width = WIDTH
image_height = HEIGHT
# Packed Field:
# Bit 7: Local Color Table Flag = 0 (no LCT)
# Bit 6: Interlace Flag = 0 (not interlaced)
# Bit 5: Sort Flag = 0
# Bits 4-3: Reserved = 00
# Bits 2-0: Size of LCT = 000 (ignored)
# Packed Field = 00000000 = 0x00
packed_id_fields = 0x00

gif_bytes.extend(image_separator)
gif_bytes.extend(struct.pack('<HHHH', image_left, image_top, image_width, image_height)) # Little-endian positions/dimensions
gif_bytes.append(packed_id_fields)

# 5. Image Data (LZW Min Code Size byte + LZW Data Blocks)
gif_bytes.extend(image_data_blocks)

# 6. Trailer (1 byte)
gif_bytes.extend(b';') # 0x3B

# --- Output to stdout ---
# Write the final byte array to standard output's binary buffer
sys.stdout.buffer.write(gif_bytes)

import sys
import struct

# GIF dimensions
WIDTH = 200
HEIGHT = 200

# Colors (Index 0: White, Index 1: Red)
# Palette: White (255, 255, 255), Red (255, 0, 0)
COLOR_TABLE = bytes([
    255, 255, 255,  # 0: White
    255, 0, 0,      # 1: Red
])
# We need 2 colors, so the Size of Global Color Table field (N)
# satisfies 2^(N+1) = 2, which means N+1=1, so N=0.
GCT_SIZE_N = 0 # Represents 2^(0+1) = 2 colors

# Triangle vertices (simple integer coordinates)
# Top: (100, 20)
# Bottom Left: (20, 180)
# Bottom Right: (180, 180)
v0 = (100, 20)
v1 = (20, 180)
v2 = (180, 180)

# Function to check if a point (x, y) is inside the triangle using edge functions
# Note: This defines the edges in a specific order (e.g., counter-clockwise)
# The sign of the result determines which side of the edge the point is on.
# If all signs are the same (or zero), the point is inside or on the boundary.
def edge_function(p, a, b):
    return (p[0] - a[0]) * (b[1] - a[1]) - (p[1] - a[1]) * (b[0] - a[0])

def is_inside_triangle(x, y):
    p = (x, y)
    # Check signs relative to edges v0->v1, v1->v2, v2->v0
    w0 = edge_function(p, v0, v1)
    w1 = edge_function(p, v1, v2)
    w2 = edge_function(p, v2, v0)
    # Point is inside if all edge functions are non-negative (or all non-positive, depending on winding)
    # For our chosen vertices (CCW order), inside points should yield >= 0
    return w0 >= 0 and w1 >= 0 and w2 >= 0

# Generate pixel data (list of color indices: 0 for white, 1 for red)
pixel_indices = []
for y in range(HEIGHT):
    for x in range(WIDTH):
        if is_inside_triangle(x, y):
            pixel_indices.append(1)  # Red
        else:
            pixel_indices.append(0)  # White

# --- LZW Encoding ---
# We will use a simplified LZW: just output Clear Code, then each pixel index, then EOI code.
# This is valid but not very compressed.

# LZW Minimum Code Size:
# We have 2 colors (0, 1). Need codes for colors + Clear Code + EOI Code.
# Min code size N must satisfy 2^N >= num_colors.
# 2^2 = 4 >= 2. So, N = 2.
LZW_MIN_CODE_SIZE = 2
CLEAR_CODE = 1 << LZW_MIN_CODE_SIZE  # 2^2 = 4
EOI_CODE = CLEAR_CODE + 1            # 4 + 1 = 5

# Bit packing variables
lzw_encoded_bytes = bytearray()
bit_buffer = 0
bits_in_buffer = 0
# Initial code size for *output* stream is LZW_MIN_CODE_SIZE + 1
current_code_size = LZW_MIN_CODE_SIZE + 1 # 3 bits initially

# Helper to write codes to the bit buffer and flush bytes when full
def write_code(code):
    global bit_buffer, bits_in_buffer
    bit_buffer |= (code << bits_in_buffer)
    bits_in_buffer += current_code_size
    while bits_in_buffer >= 8:
        byte = bit_buffer & 0xFF
        lzw_encoded_bytes.append(byte)
        bit_buffer >>= 8
        bits_in_buffer -= 8

# --- Start LZW Stream ---
# 1. Write Clear Code
write_code(CLEAR_CODE)

# 2. Write pixel data indices as codes
for index in pixel_indices:
    write_code(index) # Codes 0 and 1

# 3. Write End of Information Code
write_code(EOI_CODE)

# 4. Flush any remaining bits in the buffer
if bits_in_buffer > 0:
    byte = bit_buffer & 0xFF
    lzw_encoded_bytes.append(byte)

# --- Format LZW data into blocks ---
# Blocks are prefixed with a byte indicating size (1-255), ending with a 0-size block.
image_data_blocks = bytearray()
image_data_blocks.append(LZW_MIN_CODE_SIZE) # Start with the LZW Min Code Size byte

offset = 0
while offset < len(lzw_encoded_bytes):
    chunk_size = min(255, len(lzw_encoded_bytes) - offset)
    image_data_blocks.append(chunk_size) # Size byte
    image_data_blocks.extend(lzw_encoded_bytes[offset : offset + chunk_size]) # Data bytes
    offset += chunk_size

image_data_blocks.append(0) # Zero-length block to end data sub-blocks

# --- Assemble the GIF File ---
gif_bytes = bytearray()

# 1. Header (6 bytes)
gif_bytes.extend(b'GIF89a')

# 2. Logical Screen Descriptor (7 bytes)
packed_lsd_fields = 0b10000000 # Bit 7: GCT Flag=1; Bits 6-4: Color Res=000 (1 bit/color - WRONG, should be 7=111 for 8bit); Bit 3: Sort=0; Bits 2-0: Size of GCT = GCT_SIZE_N
# Corrected Packed Field:
# Bit 7: Global Color Table Flag = 1 (present)
# Bits 6-4: Color Resolution = 111 (8 bits per primary color)
# Bit 3: Sort Flag = 0 (GCT is not sorted)
# Bits 2-0: Size of Global Color Table = GCT_SIZE_N (0 -> table size is 2^(0+1)=2)
# Packed Field = 1 111 0 000 = 0xF0
packed_lsd_fields = 0xF0
background_color_index = 0 # White
pixel_aspect_ratio = 0 # Unspecified

gif_bytes.extend(struct.pack('<HH', WIDTH, HEIGHT)) # Little-endian Width, Height
gif_bytes.append(packed_lsd_fields)
gif_bytes.append(background_color_index)
gif_bytes.append(pixel_aspect_ratio)

# 3. Global Color Table (GCT_SIZE_N implies 2 colors * 3 bytes/color = 6 bytes)
gif_bytes.extend(COLOR_TABLE)

# 4. Image Descriptor (10 bytes)
image_separator = b',' # 0x2C
image_left = 0
image_top = 0
image_width = WIDTH
image_height = HEIGHT
# Packed Field:
# Bit 7: Local Color Table Flag = 0 (no LCT)
# Bit 6: Interlace Flag = 0 (not interlaced)
# Bit 5: Sort Flag = 0
# Bits 4-3: Reserved = 00
# Bits 2-0: Size of LCT = 000 (ignored)
# Packed Field = 00000000 = 0x00
packed_id_fields = 0x00

gif_bytes.extend(image_separator)
gif_bytes.extend(struct.pack('<HHHH', image_left, image_top, image_width, image_height)) # Little-endian positions/dimensions
gif_bytes.append(packed_id_fields)

# 5. Image Data (LZW Min Code Size byte + LZW Data Blocks)
gif_bytes.extend(image_data_blocks)

# 6. Trailer (1 byte)
gif_bytes.extend(b';') # 0x3B

# --- Output to stdout ---
# Write the final byte array to standard output's binary buffer
sys.stdout.buffer.write(gif_bytes)