solution

Khác với việc mô phỏng một chương trình đang chạy tuần tự qua các lệnh BEGIN/END, bài này cho trước TRỰC TIẾP cấu trúc cây phạm vi (scope tree) mà trình biên dịch đã dựng sẵn khi phân tích cú pháp — giống như cách một trình biên dịch thực sự gắn một bảng ký hiệu cho mỗi nút trong cây cú pháp trừu tượng (AST).

Có $m$ phạm vi, đánh số từ $1$ đến $m$. Phạm vi $1$ là phạm vi TOÀN CỤC (không có phạm vi cha). Với mỗi phạm vi $i$ từ $2$ đến $m$, cho biết $p_i$ ($1 \le p_i < i$) là phạm vi CHA trực tiếp của phạm vi $i$ (một phạm vi có thể có nhiều phạm vi con — ví dụ hai khối if và else cùng lồng trong một khối cha sẽ là hai phạm vi con, không phải cha con của nhau).

Cho $k$ khai báo biến, mỗi khai báo có dạng <scope_id> <ten> <kieu> nghĩa là trong phạm vi <scope_id>, biến <ten> được khai báo với kiểu <kieu>. Dữ liệu đảm bảo trong cùng một phạm vi, mỗi tên biến chỉ được khai báo tối đa một lần.

Cho $q$ truy vấn, mỗi truy vấn có dạng <scope_id> <ten>: hãy phân giải tên <ten> NHÌN TỪ phạm vi <scope_id> — tìm <ten> trong chính phạm vi đó, nếu không có thì tìm tiếp ở phạm vi cha, ông, ... lên đến phạm vi toàn cục. In ra kiểu <kieu> tìm được, hoặc UNDECLARED nếu không tìm thấy ở bất kỳ phạm vi nào trên đường đi lên gốc.

Ví dụ: với $m = 4$, dãy cha $p_2\ p_3\ p_4 = 1\ 1\ 3$ (phạm vi $2$ và $3$ đều con của $1$; phạm vi $4$ là con của $3$), khai báo 1 g int và 3 a bool, truy vấn 3 g (đi lên $3 \to 1$, tìm thấy g ở gốc) trả về int; truy vấn 2 a (đi lên $2 \to 1$, không có phạm vi $3$ trên đường đi) trả về UNDECLARED vì a chỉ tồn tại trong phạm vi $3$, không phải tổ tiên của phạm vi $2$.