Làm thế nào để tìm ra mật khẩu của máy chủ CIA mà không gặp khó khăn nào? Trước hết, bạn cần phải đọc một số từ bảng điều khiển tiêu chuẩn. Sau đó, bạn có thể gửi các yêu cầu truy vấn bằng cách viết ra đầu ra tiêu chuẩn. Mỗi truy vấn phải được in trên một dòng riêng biệt và có dạng ~?~ ~a~ ~b~, trong đó ~1 \leq a \leq b \leq N~. Sau khi mỗi truy vấn đã được ghi, chương trình của bạn nên xả đầu ra và đọc câu trả lời từ đầu vào tiêu chuẩn. Câu trả lời là ~1~ nếu đoạn mật khẩu bắt đầu từ ký tự thứ ~a~ và kết thúc ở ký tự thứ ~b~ tạo thành một chuỗi dấu ngoặc hợp lệ toán học. Ngược lại, câu trả lời là ~0~. Chương trình của bạn có thể thực hiện tối đa ~Q~ truy vấn như vậy.

Sau khi chương trình của bạn đã tìm ra mật khẩu bí mật, nó nên viết ra một dòng trên đầu ra tiêu chuẩn dưới dạng ~1~ ~x_1.x_2 . . . x_N~, trong đó các ký tự ~x_1, x_2, . . . , x_N~ biểu diễn các ký tự của mật khẩu bí mật. Sau đó, chương trình của bạn nên xả đầu ra một lần nữa và kết thúc thực thi của nó một cách nhẹ nhàng.

Lưu ý: Bạn có thể tải mã nguồn mẫu từ hệ thống đánh giá có tương tác với máy chủ CIA một cách đúng đắn, bao gồm việc xả đầu ra.

Chú ý

• 14 điểm thỏa mãn ~1 \leq N \leq 1 000, Q = \frac{N^2}{4}~, toàn bộ mật khẩu là một chuỗi hợp lệ toán học.
• 7 điểm thỏa mãn ~1 \leq N \leq 1 000, Q = \frac{N^2}{4}~.
• 57 điểm thỏa mãn ~1 \leq N \leq 100 000, Q = N − 1~, toàn bộ mật khẩu là một chuỗi hợp lệ toán học.
• 22 điểm thỏa mãn ~1 \leq N \leq 100 000, Q = N − 1~.

Sample Input

? 1 6
? 1 2
? 2 4
? 2 5
? 3 4
! ((()))

Sample Output

6 9
1
0
0
1
1

Chú thích

• Mật khẩu bí mật là ((())) có độ dài 6, và một chương trình có thể yêu cầu tối đa 9 truy vấn.
• Toàn bộ mật khẩu là một chuỗi ngoặc hợp lệ toán học.
• ~((~ không hợp lệ.
• ~(()~ không hợp lệ.
• ~(())~ hợp lệ.
• ~()~ hợp lệ.
• Mật khẩu được suy ra đúng và CIA đã bị xâm nhập.