JOI-chan được chọn vào đội tuyển Nhật Bản dự thi Olympic Tin học Quốc tế. Để nâng cao kỹ năng xử lý thông tin của cô, chủ tịch K của Ủy ban Olympic Tin học Nhật Bản giao cho cô bài toán sau.

Chủ tịch K bí mật viết một chuỗi \(S\) vào sổ. Chuỗi chỉ gồm bốn ký tự <, >, [, ]. Ông đưa cho JOI-chan một tờ giấy ghi nội dung bài toán và độ dài của \(S\).

JOI-chan phải xác định \(S\) có phải một chuỗi tốt hay không. Chuỗi tốt được định nghĩa như sau:

• Chuỗi rỗng là chuỗi tốt.
• Nếu \(x\) là chuỗi tốt thì <x> là chuỗi tốt.
• Nếu \(x\) là chuỗi tốt thì [x] là chuỗi tốt.
• Nếu \(x,y\) là các chuỗi tốt thì chuỗi nối \(xy\) cũng là chuỗi tốt.
• Chỉ những chuỗi được tạo bởi các quy tắc trên mới là chuỗi tốt.

Ví dụ, <>[] và [<>]<> là chuỗi tốt; >< và [<]> không phải chuỗi tốt.

Mỗi ngày vào buổi trưa, JOI-chan được gọi cho chủ tịch K nhiều nhất một lần. Trong cuộc gọi, cô chỉ định một số nguyên \(I\) và được biết ký tự thứ \(I\) của \(S\).

JOI-chan không được ghi chép. Mỗi tối cô đi ngủ lúc 22 giờ và thức dậy lúc 6 giờ; qua giấc ngủ cô chỉ có thể ghi nhớ \(22\) bit thông tin. Chính xác hơn, trước khi ngủ cô có thể ghi nhớ một số nguyên từ \(0\) đến \(2^{22}-1\), và ngày hôm sau chỉ được dựa vào số đã nhớ. Cô luôn có thể xem độ dài \(S\) trên tờ giấy.

Thay vì ghi nhớ một số trước khi ngủ, JOI-chan có thể gửi email trả lời rằng \(S\) là hoặc không phải là chuỗi tốt; khi đó bài toán kết thúc. Nếu không gửi câu trả lời trong vòng \(15\,000\) ngày kể từ khi bắt đầu, cô bị chấm sai.

Yêu cầu

Cài đặt chiến lược của JOI-chan để luôn trả lời đúng.

Giao diện nộp bài

Nộp một tệp C++ cài đặt hàm sau:

#include "Memory_lib.h"

int Memory(int N, int M);

Hệ thống cung cấp:

char Get(int I);

Hàm Memory

int Memory(int N, int M);

Hàm mô tả hành động của JOI-chan trong một ngày:

• N là độ dài chuỗi \(S\).
• M là số được ghi nhớ từ đêm trước. Khi bắt đầu bài toán, M = 0.
• Trong mỗi lần gọi Memory, được gọi Get nhiều nhất một lần.
• Giá trị trả về phải thuộc \([0,2^{22}-1]\), hoặc bằng -1, hoặc bằng -2. Trả giá trị khác gây Wrong Answer [1].
• Trả một số trong \([0,2^{22}-1]\) nghĩa là ghi nhớ số đó trước khi ngủ.
• Trả -1 nghĩa là kết luận \(S\) là chuỗi tốt.
• Trả -2 nghĩa là kết luận \(S\) không phải chuỗi tốt.

Hành vi của Memory phải chỉ phụ thuộc vào N, M và giá trị trả về của Get nếu hàm này được gọi. Trong chấm chính thức, Memory được gọi tổng cộng \(2^{22}\cdot 4\) lần ở giai đoạn dựng bảng chuyển trạng thái.

Hàm Get

char Get(int I);

• Chỉ được gọi nhiều nhất một lần trong mỗi lần gọi Memory; gọi từ hai lần trở lên gây Wrong Answer [2].
• Phải có \(1 \le I \le N\); nếu không, gây Wrong Answer [3].
• Hàm trả về ký tự thứ \(I\) của \(S\).

Quy trình chấm

Mỗi tệp chấm chứa nhiều testcase có cùng độ dài \(N\). Nếu phát hiện lỗi, việc chấm dừng ngay.

1. Dựng bảng hành vi

Với mỗi \(M\) thỏa \(0 \le M \le 2^{22}-1\), bộ chấm thực hiện:

1. Với từng \(c\) trong <, >, [, ], gọi Memory(N,M). Nếu Memory gọi Get, bộ chấm cho Get trả về \(c\). Gọi giá trị Memory trả về là \(m(M,c)\).
2. Trong bốn lần gọi ứng với cùng \(M\), quyết định có gọi Get hay không phải giống nhau. Nếu có gọi, cả bốn lần phải gọi với cùng chỉ số \(I\). Nếu không gọi, cả bốn lần phải trả cùng một giá trị. Vi phạm gây Wrong Answer [4]. Gọi chỉ số đó là \(i(M)\); nếu không gọi Get, quy ước \(i(M)=1\).

2. Mô phỏng từng chuỗi

Với mỗi testcase \(S\):

1. Đặt \(M=0\).
2. Lặp các bước sau:
3. Đặt \(c=S_{i(M)}\).
4. Thay \(M\) bằng \(m(M,c)\).
5. Nếu \(M=-1\) hoặc \(M=-2\), chuyển sang kiểm tra kết luận.
6. Nếu đã thực hiện \(15\,000\) bước mà chưa kết luận, gây Wrong Answer [5].
7. Gây Wrong Answer [6] nếu \(S\) tốt nhưng \(M=-2\), hoặc \(S\) không tốt nhưng \(M=-1\).

Nếu tất cả testcase đều hợp lệ, bài nộp được chấp nhận.

Chỉ giai đoạn dựng bảng hành vi được tính thời gian và bộ nhớ trong cách chấm chính thức. Tất cả \(2^{22}\cdot4\) lần gọi Memory ở giai đoạn này phải tránh Wrong Answer [1], [2], [3] và lỗi thực thi.

Ràng buộc

• \(1 \le |S| \le 100\).
• Mọi ký tự của \(S\) thuộc tập {<, >, [, ]}.

Phân nhóm

• Nhóm 1 (10 điểm): \(|S| \le 8\)
• Nhóm 2 (10 điểm): \(|S| \le 14\)
• Nhóm 3 (5 điểm): \(|S| \le 24\)
• Nhóm 4 (5 điểm): \(|S| \le 30\)
• Nhóm 5 (10 điểm): Mọi ký tự của \(S\) là < hoặc >
• Nhóm 6 (60 điểm): Không có ràng buộc bổ sung

Ví dụ

4 1
<>[]

-1