E. Eureka!
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

The king has received $$$n$$$ chests, one from each of $$$n$$$ neighboring empires. Each chest contains exactly $$$m$$$ ($$$m \ge n$$$) identical-looking nuggets.

The king's advisor reveals that exactly one of these chests is filled with only counterfeit nuggets, while the remaining $$$n-1$$$ chests contain only real gold.

Each real gold nugget weighs $$$r$$$ grams (where $$$r \ge 2$$$), and each counterfeit nugget weighs $$$f$$$ grams (where $$$1 \le f \lt r$$$).

You have access to a single, precise balance scale. You can take any number of nuggets from each chest and place them on the scale to find their total combined weight. However, the scale is a delicate prototype and can be used at most once before it breaks.

As the royal scientist, you must identify which empire sent the counterfeit chest.

Input

Each test contains multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \le t \le 1000)$$$ — the number of test cases. The description of test cases follows.

The only line contains four integers $$$n, m, r, f$$$ $$$(1 \le n \le 10^4, n \le m \le 10^5, 1 \le f \lt r \le 10^5)$$$ — the number of chests, the number of nuggets in each chest, the weight of each real nugget, and the weight of each fake nugget, respectively.

It is guaranteed that the sum of $$$n$$$ overall test cases is not greater than $$$10^4$$$.

Interaction

To make a measurement, output ? followed by $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le m$$$ for $$$i = 1,2,\dots,n$$$), where $$$a_i$$$ represents the number of nuggets from the chest from empire $$$i$$$ you wish to put on the balance.

In response to this measurement, you will receive the total weight of the $$$\sum_{i=1}^n a_i$$$ nuggets on the balance. Remember that you may take at most one measurement. If you make more than one measurement, you will receive the Wrong Answer verdict.

To output the answer, output ! $$$i$$$ ($$$1 \le i \le n$$$), indicating that you believe empire $$$i$$$ sent the chest of fake nuggets.

After outputting a query, do not forget to output a newline and flush the output buffer. Otherwise, you will receive the verdict Idleness limit exceeded. To flush the buffer, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • see the documentation for other languages.
Examples
Input
1
5 5 5 4

55
Output
? 4 2 0 3 2

! 3
Input
2
1 100 10000 101
3 6 1000 999

12999
Output
! 1

? 1 6 6

! 1
Note

In the first example, there are 5 empires, each having sent a chest of 5 nuggets. Each real nugget weighs 5 grams, and each fake nugget weighs 4 grams. In the example, we asked to weigh 4 nuggets from the first empire's chest, 2 from the second's, none from the third's, 3 from the fourth's, and 2 from the fifth's. The interactor tells us the total weight to be 55. Since none of our choice of quantity is a multiple of 5 except 0, but 55 is a multiple of 5, empire 3 must have sent us the chest of 4-gram nuggets.

In the first test case of the second example, since there is only one empire, it must have sent the chest of fake gold.