這是一道互動題。 詢問次數上限為 $18\,000$ 次。

評測方有一個恰好由 1000 個二進位數字組成的秘密字串。在本題的每個測試中，字串都預先固定，且不會改變。你必須透過詢問找出這個字串。

每次詢問，你選擇一個區間 $[a, b]$（$1 \le a \le b \le 1000$）進行詢問。接著評測方擲一枚硬幣，給你以下兩個值之一，每種情況的機率均為 50%：

1. 區間 $[a, b]$ 中 1 的個數；
2. 從 $0$ 到 $b - a + 1$ 中，不等於這個區間中 1 的個數的一個值，以均勻隨機方式選取。

你不可以重複使用相同的詢問。本題使用的所有隨機值都服從均勻分布，且相互獨立。

互動

參賽者的程式必須輸出下列格式之一的指令，與評測程式互動：

• ? a b。詢問區間 $[a, b]$。為了回答這個詢問，評測程式會輸出一個整數：以 50% 的機率輸出區間 $[a, b]$ 中 1 的個數，否則輸出從 $0$ 到 $b - a + 1$ 中不等於該個數的一個隨機值。
• ! ans。本題的答案，其中 ans 是長度為 1000、由 0 和 1 組成的字串。輸出這個指令後，參賽者的程式應立即結束。

範例

輸入格式 1

2
3
3
1
3

輸出格式 1

? 1 3
? 1 5
? 3 5
? 2 3
? 2 5
! 01101

說明

上面的範例僅用於展示格式。在此範例中，字串長度為 5。在真正的第一筆測試以及所有其他測試中，要猜測的字串長度都恰好為 1000。