|2021-2022 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred)|
This is an interactive problem.
There is a grid of $$$n\times m$$$ cells. Two treasure chests are buried in two different cells of the grid. Your task is to find both of them. You can make two types of operations:
You need to find the treasures in at most 7 operations. This includes both DIG and SCAN operations in total. To solve the test you need to call DIG operation at least once in both of the cells where the treasures are hidden.
Your program has to process multiple test cases in a single run. First, the testing system writes $$$t$$$ — the number of test cases ($$$1\le t \le 100$$$). Then, $$$t$$$ test cases should be processed one by one.
In each test case, your program should start by reading the integers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 16$$$).
Then, your program can make queries of two types:
After you found both treasures, i. e. you received $$$1$$$ for two DIG operations, your program should continue to the next test case or exit if that test case was the last one.
1 2 3 1 1 3 0 1
SCAN 1 2 DIG 1 2 SCAN 2 2 DIG 1 1 DIG 1 3