This is an interactive problem.
Chromate has a secret positive integer $$$x$$$ ($$$1 \le x \le 10^9$$$), and wants you to guess it.
Formally, you can ask him about some positive integer $$$a$$$, and Chromate will return the value of $$$\lfloor \frac{ gcd(a,x) + lcm(a,x)}{2} \rfloor$$$ to you.
Here $$$gcd(a,x)$$$ means the greatest common divisor of $$$a$$$ and $$$x$$$, while $$$lcm(a,x)$$$ means the least common multiple of $$$a$$$ and $$$x$$$.$$$\lfloor \rfloor$$$ is the rounding symbol for downward rounding.
You must find out the value of the integer $$$x$$$ within $$$4$$$ queries. The number of queries includes the final query where $$$x=a$$$.
Before any interaction begins, you are given $$$t$$$($$$1 \le t \le 10^4$$$), the number of test cases.
During the interaction, you may ask about the integer $$$a(1 \le a \le 10^9)$$$ by "? a". The interactor will give you the integer $$$\lfloor \frac{ gcd(a,x) + lcm(a,x)}{2} \rfloor$$$(note it may be greater than $$$10^9$$$).
When your program guessed the number $$$x$$$, print string "! x", where $$$x$$$ is the answer.
Note:after printing a query do not forget to output end of line and flush the output.
To do this, use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python.
Use standard input to read the responses to the queries.
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test data.
Following lines will contain responses to your queries — the value of $$$\lfloor \frac{ gcd(a,x) + lcm(a,x)}{2} \rfloor$$$. The $$$i$$$-th line is a response to your $$$i$$$-th query. When your program will guess the number print "! x", where $$$x$$$ is the answer and terminate your program.
The testing system will allow you to read the response on the query only after your program print the query for the system and perform flush operation.
To make the queries your program must use standard output.
Your program must print the queries — "? a", one query per line (do not forget "end of line" after each query). After printing each line your program must perform operation flush.
The response to the query will be given in the input file after you flush output. In case your program guessed the number $$$x$$$, print string "! x", where $$$x$$$ — is the answer.
2 500000002 3 2 5001 51 4
? 1000000000 ? 4 ? 2 ! 2 ? 9999 ? 99 ? 6 ! 3
Yugandhar likes Diya, so he wants to tell his feelings by writing it on letter.
For simplicity letter is a $$$2D$$$ grid of $$$n$$$ rows and $$$m$$$ columns. Initially,all cells are white except for a blue cell $$$(x,y)$$$. Diya likes pink color, so Yugandhar started to put $$$k$$$ pink drops on $$$k$$$ different cells which are white.
After that,the following two events occur alternately in order,until every cell become either blue or pink.
- Cells adjacent to all blue cells which are white becomes blue.
- Cells adjacent to all pink cells which are white become pink.
Help Yugandhar by telling him what the maximum pink cells he will get if he choose $$$k$$$ cells optimally.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10$$$). The description of the test cases follows.
The first line of each testcase contains two integers $$$n,m$$$ ($$$1 \le n,m \le 10^9$$$), the dimensions of letter.
The second line of each testcase contains three integers $$$x,y,k$$$ ($$$1 \le x \le n$$$, $$$1 \le y \le m$$$, $$$0 \le k \le nm-1$$$), the coordinates of blue drop and number of cells he have to put pink drops.
For each test case, print a single integer — the maximum pink cells he will get if he choose $$$k$$$ cells optimally.
41 11 1 02 21 2 12 32 1 54 53 4 2
0 2 5 16
In the first test case,you can't get any pink cell.
In the second test case, initially $$$(1,2)$$$ is blue.
The optimal selection for $$$k=1$$$ is $$$(2,2)$$$.After choosing $$$(2,2)$$$ the following happens:
- $$$(1,1)$$$ becomes blue;
- $$$(2,1)$$$ becomes pink.
The maximum pink cells we obtained is $$$2$$$ which are $$$(2,1)$$$ and $$$(2,2)$$$.
Han hasn't eaten since 2 months ago. She had planned to eat some salmon in George's house.
George has $$$n$$$ boxes where there are $$$a_i$$$ salmons in every box $$$1 \leq i \leq n$$$.Initially,Han's score is $$$0$$$ and she starts by standing in front of box $$$1$$$.She's trying to eat all of George's salmons with the procedure as below:
- If she's now in front of box $$$i$$$ and there's still salmon inside the box $$$(a_i \gt 0)$$$, she will eat $$$1$$$ salmon and her score increases by $$$1$$$. The number of salmon inside the box will decrease by $$$1$$$ $$$(a_i := a_i - 1)$$$. If there's no salmon inside the box $$$(a_i = 0)$$$, she will skip this step;
- Move to the next box. If she's currently in front of box $$$i$$$, she will move into box $$$(i\mod n)+1$$$;
- Go back to step 1.
She wants to know, for each index $$$i$$$ from $$$1$$$ to $$$n$$$, what is her score as soon as there is no salmon in box $$$i$$$?
The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4) $$$ — the number of test cases. Descriptions of the test cases follow.
The first line of each test case contains a single integer $$$n$$$ $$$(1 \leq n \leq 2 \times 10^5)$$$, the number of boxes.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$ — the number of salmons in each box.
The sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^5$$$.
For each test case, print $$$n$$$ integers — the answer for each index $$$i$$$ $$$(1 \leq i \leq n)$$$.
342 1 4 345 3 2 152 5 7 4 6
5 2 10 9 11 9 7 4 6 19 24 17 23
You are given a directed graph with $$$n$$$ nodes and $$$m$$$ edges. The color of the $$$i$$$-th edge is $$$c_i$$$.
We call a path (does not have to be a simple path) colorful iff it does not have two consecutive edges of the same color.
Find all nodes $$$x$$$ such that there exist a colorful path starting from $$$1$$$ and ending at $$$x$$$.
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^6$$$, $$$0 \le m \le 10^6$$$) — the number of nodes and the number of edges.
Next $$$m$$$ lines describe edges: $$$i$$$-th line contains three integers $$$u_i, v_i, c_i$$$ ($$$1 \le u_i, v_i, \le n$$$; $$$u_i \ne v_i$$$; $$$1 \le c_i \le m$$$) — defining the edge from $$$u_i$$$ to $$$v_i$$$ of color $$$c_i$$$.
The sum of $$$n$$$ and the sum of $$$m$$$ over all test cases does not exceed $$$10^6$$$.
For each test case, output all the nodes $$$x$$$ such that there exist a colorful path starting from $$$1$$$ and ending at $$$x$$$ in ascending order.
45 61 2 12 3 12 4 24 2 33 4 33 5 13 21 3 12 1 15 51 2 12 3 23 4 34 2 22 5 11 0
1 2 3 4 1 3 1 2 3 4 5 1
You are given $$$3$$$ arrays $$$a, b, c$$$ of size $$$n$$$.
Your task is to construct a permutation $$$p$$$ of size $$$n$$$ to maximize the value of the permutation $$$p$$$.
The value of a permutation $$$p$$$ is defined as $$$\sum_{{p_{i}} \lt i} a_i$$$ + $$$\sum_{{p_{i}} = i} b_i$$$ + $$$\sum_{{p_{i}} \gt i} c_i$$$.
The first line contains one positive integer $$$t$$$ ($$$1 \le t \le 30000$$$) — the number of test cases. Then $$$t$$$ test cases follow.
Each test case begins with a line containing one integer $$$n$$$ ($$$1 \le n \le 200000$$$) — the number of elements in each array $$$a, b$$$ and $$$c$$$.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), the array $$$a$$$.
The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^9$$$), the array $$$b$$$.
The fourth line of each test case contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 10^9$$$), the array $$$c$$$.
The sum of $$$n$$$ over all test cases does not exceed $$$200000$$$.
For each test case, output a permutation $$$p$$$ you constructed in a single line.
If there are multiple solutions, output any.
334 4 13 3 32 4 269 9 8 2 4 43 5 3 9 9 82 4 4 8 5 3103 1 4 1 5 9 2 6 5 35 8 9 7 9 3 2 3 8 46 2 6 4 3 3 8 3 2 7
1 2 3 3 1 2 4 5 6 6 2 3 4 5 1 8 7 9 10
In the first testcase,
- $$$p_1 = 1 = 1$$$.
- $$$p_2 = 2 = 2$$$.
- $$$p_3 = 3 = 3$$$.
Therefore, the value of this permutation is $$$b_1+b_2+b_3 = 3+3+3 = 9$$$, and we can prove this is optimal.
In the second testcase,
- $$$p_1 = 3 \gt 1$$$.
- $$$p_2 = 1 \lt 2$$$.
- $$$p_3 = 2 \lt 3$$$.
- $$$p_4 = 4 = 4$$$.
- $$$p_5 = 5 = 5$$$.
- $$$p_6 = 6 = 6$$$.
Therefore, the value of this permutation is $$$c_1+a_2+a_3+b_4+b_5+b_6 = 2+9+8+9+9+8 = 45$$$, and we can prove this is optimal.
There are $$$n$$$ points $$$a_1,a_2,\dots,a_n$$$ inside the cartesian grid, where for each integer $$$1 \leq i \leq n$$$, $$$a_i$$$ is located at the coordinate $$$(x_i,y_i)$$$. No two points share the same coordinates.
You want to cover all of the points with a regular polygon which has $$$m$$$ sides. However, you have to place the center of the polygon at the coordinate $$$(0,0)$$$. You can place the polygon at any rotational orientation.
Define the size of the regular polygon as the distance between the center point of the polygon (or in this case, the coordinate $$$(0,0)$$$) and one of the vertices of the polygon. Find the minimum size of the polygon such that there exist a way to covers all $$$n$$$ points with it.
The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 3 \cdot 10^4$$$) — the number of test cases.
The first line of each test cases contains two integers $$$n,m$$$ ($$$2 \leq n \leq 2 \cdot 10^5, 3 \leq m \leq 3000$$$) — the number of points and the number of sides on the polygon.
For the next $$$n$$$ lines of each test cases, each line contains two integers $$$x_i,y_i$$$ ($$$-2 \cdot 10^4 \leq x_i,y_i \leq 2 \cdot 10^4$$$) — the coordinate of $$$a_i$$$.
It is guaranteed that $$$(x_i,y_i) \neq (x_j,y_j)$$$ for each $$$1 \leq i \lt j \leq n$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output a single real number — the minimum size of the polygon.
Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-9}$$$ — formally, if your answer is $$$a$$$, and the jury's answer is $$$b$$$, your answer will be accepted if $$$\frac{|a−b|}{\max(1,b)} \leq 10^{−9}$$$.
32 30 43 -25 40 00 11 00 -1-1 03 58 1-5 5-4 -7
4 1 8.844723953
For the first test case, the points and the polygon looks like this: 
If the size of the polygon is less than $$$4$$$, the point $$$a_1$$$ cannot be covered by the polygon no matter how the polygon is placed. Thus, the minimum size of the polygon is $$$4$$$.
For the second test case, the points and the polygon looks like this: 