#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

#define MAX 100000


char *stack[100000];
int top = -1;

void push(char *tag) {
    stack[++top] = strdup(tag); // copy string
}

char* pop() {
    if (top < 0) return NULL;
    return stack[top--];
}

int isValidTagName(char *tag) {
    for (int i = 0; tag[i]; i++) {
        if (!islower(tag[i])) return 0; // only lowercase letters
    }
    return 1;
}

char* extractTag(const char *line, int *i) {
    int start = *i + 1; 
    int end = start;

    while (line[end] && line[end] != '>') end++;

    if (line[end] != '>') return NULL; // no closing '>'

    int len = end - start;
    char tag = (char)malloc(len + 1);
    strncpy(tag, line + start, len);
    tag[len] = '\0';

    *i = end; // move index to '>'
    return tag;
}

void checkLine(char *line) {
    top = -1;
    int len = strlen(line);

    for (int i = 0; i < len; i++) {
        if (line[i] == '<') {
            char *tag = extractTag(line, &i);
            if (!tag) {
                printf("Invalid input\n");
                return;
            }

            if (tag[0] == '/') {  
               
                char *openTag = pop();
                if (!openTag) {
                    printf("Unbalanced\n");
                    free(tag);
                    return;
                }
                if (strcmp(openTag, tag + 1) != 0) {
                    printf("Unbalanced\n");
                    free(openTag);
                    free(tag);
                    return;
                }
                free(openTag);
            } else {
                
                if (!isValidTagName(tag)) {
                    printf("Invalid input\n");
                    free(tag);
                    return;
                }
                push(tag);
            }
            free(tag);
        } else if (!isalnum(line[i]) && !isspace(line[i])) {
            
            printf("Invalid input\n");
            return;