int main() {
    int num_changes;
    if (scanf("%d", &num_changes) != 1 || num_changes <= 0 || num_changes > MAX_CHANGES) {
        printf("Invalid input\n");
        return 1;
    }

    Node* head = NULL;
    Node* tail = NULL;

    for (int i = 0; i < num_changes; i++) {
        char input_char;
        // Consume any leftover newline characters from previous scanf
        while ((input_char = getchar()) != '\n' && input_char != EOF); 
        
        char operation_type;
        if (scanf("%c", &operation_type) != 1) {
            printf("Invalid input\n");
            return 1;
        }

        if (operation_type == 'R') { // Removal operation
            int removed_color = removeLantern(&head, &tail);
            if (removed_color == -1) {
                printf("the chain was empty\n");
            } else {
                printf("%d\n", removed_color);
            }
        } else if (operation_type == 'A') { // Addition operation
            int color_code;
            if (scanf("%d", &color_code) != 1 || color_code < MIN_COLOR_CODE || color_code > MAX_COLOR_CODE) {
                printf("Invalid input\n");
                return 1;
            }
            addLantern(&head, &tail, color_code);
        } else {
            printf("Invalid input\n");
            return 1;
        }
    }

    // Clean up remaining nodes in the list
    Node* current = head;
    while (current != NULL) {
        Node* next = current->next;
        free(current);
        current = next;
    }

    return 0;
}