#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>

#define MAX_ITEMS 1024
#define ITEMS_PER_WORD 16

typedef struct {
    uint32_t data[MAX_ITEMS / ITEMS_PER_WORD]; 
    int top;
} BitStack;

void init_stack(BitStack *s) {
    s->top = 0;
    memset(s->data, 0, sizeof(s->data));
}

int encode(char c) {
    switch(c) {
        case '(': return 0;
        case '{': return 1;
        case '[': return 2;
        default: return 3;
    }
}

char decode(int code) {
    switch(code) {
        case 0: return '(';
        case 1: return '{';
        case 2: return '[';
        default: return '?';
    }
}

bool push(BitStack *s, char c) {
    if (s->top >= MAX_ITEMS) return false;

    int code = encode(c);
    int word_idx = s->top / ITEMS_PER_WORD;
    int bit_offset = (s->top % ITEMS_PER_WORD) * 2;

    s->data[word_idx] &= ~((uint32_t)0x3 << bit_offset);
    s->data[word_idx] |= ((uint32_t)code << bit_offset);

    s->top++;
    return true;
}

char pop(BitStack *s) {
    if (s->top <= 0) return '\0';

    s->top--;

    int word_idx = s->top / ITEMS_PER_WORD;
    int bit_offset = (s->top % ITEMS_PER_WORD) * 2;
    int code = (s->data[word_idx] >> bit_offset) & 0x3;

    return decode(code);
}

bool is_empty(BitStack *s) {
    return s->top == 0;
}

bool check_bracket(char *str) {
    BitStack s;
    init_stack(&s);

    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        char ch = str[i];

        if (ch == '(' || ch == '{' || ch == '[') {
            if (!push(&s, ch)) {
                printf("Error: Stack Overflow\n");
                return false;
            }
        } 
        else if (ch == ')' || ch == '}' || ch == ']') {
            if (is_empty(&s)) return false;

            char open_ch = pop(&s);
            
            if (ch == ')' && open_ch != '(') return false;
            if (ch == '}' && open_ch != '{') return false;
            if (ch == ']' && open_ch != '[') return false;
        }
    }

    return is_empty(&s);
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        printf("Usage: bracket <string>\n");
        return 1;
    }

    if (check_bracket(argv[1])) {
        printf("Valid\n");
        return 0;
    } else {
        printf("Invalid\n");
        return 1;
    }
}