You are the coach of a competitive programming team with $$$n$$$ members. After months of intense training, your team is ready for the "Annual International Coding Pageant" (AICP). In this tournament, teams compete against each other in a series of one-on-one matches.
The tournament structure is peculiar. There are $$$m$$$ other teams, and your team will play against each of them. For every match against an opponent team, the players are lined up, and the $$$i$$$-th player from your team competes against the $$$i$$$-th player from the opponent's team.
Each of your team members has a known strength value. The opponent teams have already submitted their player arrangements, and these are fixed. Your task is to find a single, optimal arrangement for your own team members that will be used against all m opponent teams to maximize your total score across the entire tournament.
You have a team of $$$n$$$ members with strengths given by an array of size $$$n$$$. You are competing against $$$m$$$ other teams. The $$$k$$$-th opponent team (for $$$k$$$ from $$$1$$$ to $$$m$$$) also has $$$n$$$ members, with strengths given by $$$b_{k,1}, b_{k,2}, ..., b_{k,n}$$$.
You need to find a permutation$$$^{\text{∗}}$$$ $$$p$$$ of length $$$n$$$. This permutation $$$p$$$ will be your team's final arrangement for all matches. When your team (arranged as $$$p$$$) competes against opponent team $$$k$$$, your player at position $$$i$$$ (with strength $$$a_{p_i}$$$) is matched against their player at position $$$i$$$ (with strength $$$b_{k,i}$$$).
The outcome of an individual competition between a player of strength $$$s_1$$$ and a player of strength $$$s_2$$$ is determined as follows:
Your team's total score is the sum of points from all individual competitions. That is, the sum of scores for each of your $$$n$$$ players against their counterparts in all $$$m$$$ opponent teams.
Your goal is to find the arrangement $$$p$$$ that maximizes this total score.
$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).
The first line contains two integers, $$$n$$$ ($$$1 \le n \le 20$$$) and $$$m$$$ ($$$1 \le m \le 5\,000$$$), the number of members per team and the number of opponent teams.
The second line contains n space-separated integers $$$a_1, a_2, ..., a_n$$$, representing the strengths of your team members ($$$1 \le a_i \le 10^9$$$).
The next $$$m$$$ lines each contain n space-separated integers. The $$$k$$$-th of these lines represents the strengths of the $$$k$$$-th opponent team: $$$b_{k,1}, b_{k,2}, ..., b_{k,n}$$$ ($$$1 \le b_{k,i} \le 10^9$$$).
Print a single line containing $$$n$$$ space-separated integers, representing the optimal arrangement of your team's strengths that maximizes the total score. If multiple optimal arrangements exist, any one of them will be accepted.
Formally, let $$$p$$$ be the optimal permutation, you must output $$$a_{p_1},a_{p_2},\dots,a_{p_n}$$$ separated by whitespace in a single line.
2 2 10 20 15 5 12 18
20 10
Your team has strengths $$$[10, 20]$$$. There are two opposing teams.
If you use the arrangement $$$p=[1,2]$$$, the strength of the team is $$$[10, 20]$$$:
If you use the arrangement $$$p=[2,1]$$$, the strength of the team is $$$[20, 10]$$$:
The arrangement $$$[20, 10]$$$ yields a higher total score and is the optimal answer.
Summer vacation has arrived, and Nobita is once again dreaming of an exciting adventure. Instead of studying for exams or doing homework, he imagines drifting peacefully in a hot-air balloon across the mountains that stretch endlessly beyond his town. Of course, when it comes to turning dreams into reality, there is only one person he can rely on: Doraemon.
The mountains Nobita wants to cross are arranged in a straight line, and each one has a specific height. For convenience, Doraemon numbers the mountains from $$$1$$$ to $$$n$$$, and Nobita writes down their current heights in a notebook. The height of the mountain $$$i$$$ is $$$a_i$$$. At first glance, the plan seems simple: launch the balloon at one mountain, then float to the next, and keep going until the desired destination.
But the balloon journey is not smooth. Each time the balloon moves from one mountain to the next, the balloon must rise or sink to match the new height. The effort required is the difference of the two mountain heights. If the next mountain is nearly the same height as the current one, the balloon moves gently. If the difference is large, the balloon struggles and the journey becomes more costly. Nobita quickly realizes that calculating the total effort for a long trip is not easy at all.
Doraemon, seeing Nobita's frustration, pulls out yet another gadget from his pocket. This one has the power to increase the heights of an entire stretch of mountains all at once. With just a flick, Doraemon can make a group of mountains taller. Naturally, Nobita becomes excited because this means he can reshape the mountains before planning his balloon routes. But now the situation is even more complex: the mountain heights are changing, and Nobita still wants to know the cost of his planned trips.
You are given a sequence of operations, describing either Doraemon's gadget use or Nobita's trip queries. There are two types of operations:
Your task is to follow this summer adventure, processing every operation in the given order. When Nobita asks about a trip, you must calculate and report the correct cost at that moment.
The first line of input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 3 \cdot 10^5$$$) — the number of mountains and the number of queries.
The second line of input contains n integers $$$a_1,\dots ,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the height of the mountains.
The next q lines contain query descriptions. Each of them contains integers $$$t, l, r$$$ and may contain $$$x$$$ ($$$1 \le t_i \le 2, 1 \le l \le r \le n, 1 \le x_i \le 10^9$$$). Here $$$t = 1$$$ corresponds to the gadget boost and $$$t = 2$$$ corresponds to the trip query.
It's guaranteed that the input will contain at least one trip query.
For each trip query, print the answer.
5 65 1 4 4 72 1 51 2 4 32 1 52 3 31 3 5 22 2 4
10 4 0 5
10 99 3 18 11 17 19 10 7 10 181 1 2 101 6 8 82 2 91 9 9 101 6 10 151 2 7 42 1 101 1 4 142 3 8
45 68 56
One day, Nobita was asking Doraemon for new gadgets. Their friend, CK Chang, came to visit and heard them talking about going shopping at the 22nd Century Department Store.
CK Chang, who is very smart about money, shared his own special rule. "Doraemon," he said, "I have a rule that helps me buy a lot of things. It's CK Chang's 10x Rule: never buy an item unless you have at least 10 times its price in your pocket before you buy it."
Doraemon thought this was an interesting rule and decided to use it. For example, to buy a "Hopter" (Bamboo Copter) that costs $30, he must have at least $300 in his pocket. After buying it, his money would go down by $30, leaving him with $270.
Doraemon has some money and a list of cool gadgets he wants to buy for Nobita. To get the most items possible, he needs your help.
Your job is to find out the maximum number of gadgets Doraemon can get if he follows CK Chang's 10x Rule. You'll need to figure out the best order for him to buy them in.
The first line contains two integers, $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5, 1 \le m \le 10^{15}$$$) — $$$n$$$ is the number of gadgets available, and $$$m$$$ is the money Doraemon has at start.
The second line has $$$n$$$ numbers: $$$p_1, p_2, ..., p_n$$$ ($$$1 \le p_i \le 10^9$$$) — the price of gadgets.
Output a single integer — the maximum number of gadgets Doraemon can buy.
5 1001 2 4 5 8
5
3 10011 10 12
1
In a vast and mysterious world lies an infinite two-dimensional grid. Each location in this grid is identified by integer coordinates $$$(x, y)$$$. You have been informed that a demon is hiding somewhere in this grid, and your mission is to find the exact position of the demon before it disappears forever.
You have received $$$n$$$ clues from ancient observers who tried to track the demon's movement. Each clue is described by three integers $$$(x_i, y_i, d_i)$$$, meaning that the demon is at a Cartesian distance of $$$\sqrt{d_i}$$$ from the point $$$(x_i, y_i)$$$. However, the demon is a master of illusions, so not all clues can be trusted. The demon has created shadow replicas of itself at certain locations, causing some clues to be either real or fake followed by these conditions: if a clue is real, the demon's actual position must exactly match the distance indicated by that clue's coordinates and distance value; if a clue is fake, the demon's position must not match that distance.
Unfortunately, you do not know which clues are real and which are fake. To ensure that the demon can be captured, you have to find the maximum number of real clues that allows you to locate the demon's position without needing to know in advance which clues are real.
Formally, let $$$c_i$$$ represent clue $$$(x_i,y_i,d_i)$$$. Suppose the demon is located at position $$$o = (o_x,o_y)$$$, the reality of a clue is defined as follows:
The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$
The next $$$n$$$ lines contain clues. Each contains three integers $$$x_i, y_i, d_i$$$ $$$(-10^5 \leq x_i, y_i \leq 10^5, 1 \leq d_i\leq 10^5)$$$
It is guaranteed that the demon's coordinates must be integers.
If no solution exists, print -1.
Otherwise, print two lines. On the first line, print the maximum number $$$k$$$ of real clues that satisfy the conditions. On the second line, print two space-separated integers representing the demon's position: $$$o_x$$$ and $$$o_y$$$.
415 0 921 0 92 0 138 0 13
2 18 0
80 0 250 10 255 5 2520 0 2520 10 2525 5 2510 -10 1618 -10 16
-1
80 0 251 0 162 0 910 0 916 0 9-12 0 25-11 0 16-10 0 9
2 13 0
In the first test case:
if $$$k = 4:$$$ The only possible set includes all four clues, and this set is contradictory.
if $$$k = 3:$$$ There are four possible sets of three clues, and all of them are contradictory.
if $$$k = 2:$$$
if $$$k = 1:$$$ Choosing any single clue is ambiguous, resulting in multiple solutions.
Therefore, the maximum number of clues that satisfy the conditions is $$$2$$$, and the corresponding demon position is $$$(18, 0)$$$.
In the second test case:
If $$$k \ge 4$$$: It is easy to see that there is no way to choose $$$k$$$ clues such that they determine a position.
if $$$k = 3$$$: There are two possible ways to select three clues that determines a position
if $$$k = 2$$$: There are five possible ways to select two clues that determine a position:
if $$$k = 1$$$: Choosing any single clue is ambiguous, resulting in multiple solutions.
Therefore, the result is $$$-1$$$.
An array $$$a = [a_1,a_2,\dots , a_n]$$$ of length $$$n$$$ is exotic if and only if these two conditions are satisfied.
You are given two integers $$$n$$$ and $$$m$$$. Count the number of exotic arrays $$$a$$$ of length $$$n$$$. Since the answer can be very large, print it modulo $$$10^9 + 7$$$.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
Each of the next $$$t$$$ lines contains two integers $$$n$$$, $$$m$$$ ($$$1 \le n, m \le 10^9$$$) — the length of the array and the maximum allowed value.
For each test case, print a single integer — the number of exotic arrays $$$a$$$ modulo $$$10^9 + 7$$$.
61 52 22 13 55 7998244353 1000000000
52031283724174902
In the first test case, $$$n = 1$$$. Every array of length $$$1$$$ is exotic. The answer is $$$5$$$.
In the second test case, $$$n = 2$$$, $$$m = 2$$$. The exotic arrays are $$$[1, 2]$$$ and $$$[2, 2]$$$.
In the third test case, $$$n = 2$$$, $$$m = 1$$$. No exotic arrays exist.
In the ancient land of Tetralia, a magical pyramid roams the infinite two-dimensional triangle grid. This pyramid is a regular tetrahedron (a triangular pyramid where all four faces are congruent equilateral triangles). Each of its four faces has a positive integer $$$a,b,c,d$$$ marked on it.
Initially, the pyramid stands upright at coordinate $$$(0,0)$$$, with one face with integer $$$a$$$ resting on the ground. The face with integer $$$b$$$ is facing toward the northwest, the face with integer $$$c$$$ is facing toward the northeast, and the face with integer $$$d$$$ is facing toward the south, as shown in the middle figure.
The infinite two-dimensional triangle grid and its coordinate $$$(x,y)$$$ is defined as the right figure, with the blue cell at $$$(0,0)$$$ i.e., the starting cell. The $$$+x$$$ direction is north, and the $$$+y$$$ direction is east.
The pyramid can move by flipping itself over one of the three edges of its bottom face; the edge that is used for flipping is called a pivot edge. After a flip, the pyramid lands on the new adjacent cell in the triangle grid, with the new face that contains the pivot edge as one of its sides resting on the ground. The cost of such a move is equal to the number marked on the new bottom face (the face touching the ground after the flip).
Your task is to find the minimum total cost to move the pyramid to the destination cell $$$(x,y)$$$.
The first line contains $$$4$$$ integers $$$a, b, c, d$$$ ($$$1 \le a, b, c, d \le 10^6$$$) — four faces of the pyramid.
The second line contains $$$2$$$ integers $$$x, y$$$ ($$$-10^9 \le x, y \le 10^9$$$) — the coordinates of the destination cell.
A single integer — the minimum cost to move the pyramid to the destination cell.
1 2 3 41 2
15
1 2 3 4-1 0
6
10 10 10 100 0
0
In the first test case, the image below shows one of the moves that results in the minimum cost.
The bottom face of the tetrahedron along the path is $$$a \rightarrow c \rightarrow d \rightarrow b \rightarrow c \rightarrow a \rightarrow b$$$, resulting in the total cost of $$$3 + 4 + 2 + 3 + 1 + 2 = 15$$$.
The Forgotten Caverns form a network of $$$n$$$ chambers, connected by $$$m$$$ bidirectional tunnels. This network is a connected, undirected, unweighted graph with vertices numbered from $$$1$$$ to $$$n$$$.
Each chamber $$$i$$$ has a difficulty value $$$a_i$$$. Some chambers also contain ancient treasures, indicated by $$$b_i \in \{0,1\}$$$: if $$$b_i=1$$$, there is a treasure in chamber $$$i$$$; if $$$b_i=0$$$, there is none.
You are an adventurer exploring these caverns. You begin in some chamber with magical power $$$p$$$. From your current chamber $$$u$$$, you may move to any adjacent chamber $$$v$$$ through a tunnel:
You may visit the same chamber any number of times, and you may use the same tunnel any number of times.
You are asked to process $$$q$$$ queries of the following two types:
The treasure configuration is persistent and updates after each type-2 query.
The first line contains three integers $$$n$$$, $$$m$$$, $$$q$$$ ($$$2 \le n \le 10^5$$$, $$$n-1 \le m \le 2\cdot 10^5$$$, $$$1 \le q \le 10^5$$$) — the number of chambers, tunnels, and queries respectively.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the difficulty of each chamber.
The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$b_i \in \{0,1\}$$$) — the initial treasure configuration.
The next $$$m$$$ lines each contain two integers $$$x, y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$) — a tunnel between chambers $$$x$$$ and $$$y$$$.
The next $$$q$$$ lines each describe one query:
It is guaranteed that the graph is connected, with no multiple edges and no self-loops.
It is guaranteed that there will be at least one type-1 query.
For each query of type-1, output a single integer — the minimum number of coins required.
5 7 86 12 10 15 51 0 1 0 02 34 51 33 44 15 32 51 1 61 4 152 3 41 1 61 1 92 2 41 2 201 3 10
16 0 29 14 0 4
In the first example, the difficulties are $$$a = [6,12,10,15,5]$$$ and the initial treasures are at chambers $$$\{1,3\}$$$.
The Royal Bangkok Sports Club is preparing new endurance training for special horses. The racecourse is an $$$n × m$$$ grid of rectangular fields. Each field $$$(i, j)$$$ has a difficulty rating $$$D_{i,j}$$$. A higher value means the road there is rougher and requires more effort from the horse. Some fields are soft grass, while others are bumpy and uneven, demanding very high effort. Horses can move between two fields if they share a common side (up, down, left, and right).
For training, the committee designs tasks as follows:
The effort of a training route is defined as the maximum difficulty among all fields the horse must step on during the route.
The horse may choose any order to visit the fields, and the committee only cares about the minimum possible effort. There are $$$q$$$ tasks, and you must report all of them!
The first line contains three integers $$$n, m, q$$$ $$$(1 \leq n, m \leq 500)$$$ and $$$(1 \leq q \leq 10^5)$$$.
The next $$$n$$$ lines each contain $$$m$$$ integers, giving the difficulty ratings $$$D_{i,j}$$$ of the fields.
Each of the next q lines describes one query with six integers $$$r, c, r_1, c_1, r_2, c_2$$$
For each query, print a single integer — the minimum effort required for that horse's route.
3 4 25 1 7 76 4 2 89 3 3 32 2 1 2 2 31 1 2 2 3 3
7 5
These are the moves that results in the minimum cost.
Other routes may exist, but whichever path is chosen, the minimum possible effort should be the same.
There are $$$n$$$ vertical poles standing on a straight line at integer positions $$$x = 1,2,\dots,n$$$. The $$$i$$$-th pole has height $$$h_i$$$ and is located at $$$x = i$$$.
Sunlight comes from the left and travels in the direction of the vector $$$\vec{d} = (t_x, t_y)$$$ with $$$t_x \gt 0$$$. This means the rays propagate toward increasing $$$x$$$, with vertical slope determined by $$$t_y/t_x$$$.
A pole is ray cast (its top is directly lit) if its top lies strictly above the shadow envelope formed by all poles to its left.
Your task is to count how many poles are ray cast.
The first line contains $$$t$$$ ($$$1 \le t \le 150\,000$$$) — the number of test cases.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^{5}$$$) — the number of poles.
The second line contains $$$n$$$ integers $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10^{9}$$$) — the heights of the poles.
The third line contains two integers $$$t_x$$$ and $$$t_y$$$ ($$$1 \le t_x \le 10^{9}$$$, $$$-10^{9} \le t_y \le 10^{9}$$$) — the components of the sunlight direction vector $$$\vec{d}$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^{5}$$$.
For each test case, print a single integer — the number of poles that are ray cast.
452 3 2 7 42 155 7 4 6 32 -145 5 5 53 033 10 71 -2
3 2 1 2
Figure 1 corresponds to the first test case with $$$h = [2,3,2,7,4], t_x = 2, t_y = 1$$$.
Figure 2 corresponds to the second test case with $$$h = [5,7,4,6,3], t_x = 2, t_y = -1$$$.
It's Christmas Eve! Santa Claus takes a quick trip in his time machine to visit his good friend, Doraemon, in the 22nd century. Seeing Santa so busy, Doraemon offers to help with a futuristic sleigh and some amazing gadgets!
This year, they are delivering two special items:
But Doraemon has a strict rule from his "Future Gadget Rulebook" to make sure the deliveries are perfect:
So, for each delivery, Santa must travel from Doraemon's workshop to one kid's house and come straight back to the workshop to pick up the next item. Your job is to help Santa and Doraemon find the shortest total distance they need to travel to deliver everything correctly.
You are given a map with Doraemon's workshop and all the kids' houses. The roads connect these places, and each road has a certain length. Every house is either a "Good Kid" house or a "Bad Kid" house.
Santa has to make one trip for each and every house:
Here are the two very important rules for the path from the workshop to the house, and from the house back to the workshop:
You are guaranteed that Santa can always find a way to reach every house by following these rules.
The first line has one number, $$$n$$$ ($$$1 \le n \le 10^5$$$), which is how many houses there are.
The second line has a string of $$$n$$$ letters. Each letter tells you the type of a house. 'G' is for a Good kid's house, and 'B' is for a Bad kid's house.
The third line has one number, $$$m$$$ ($$$1 \le m \le 3 \cdot 10^5$$$), which is how many roads there are on the map.
The next $$$m$$$ lines describe the roads. Each line has three numbers: $$$u$$$, $$$v$$$, and $$$d$$$ ($$$0 \le u,v \le n, 1 \le d \le 10^6$$$). This means there is a road between place $$$u$$$ and place $$$v$$$ with a distance of $$$d$$$. Place $$$0$$$ is Doraemon's workshop, and places $$$1$$$ to $$$n$$$ are the houses.
Print one single number — the shortest total distance Santa must travel for all the deliveries combined.
3GBG40 1 100 2 121 3 52 3 6
74
Nobita is in trouble again! He made a bet with the neighborhood bully, Gian, that he could win a game of Tic-Tac-Toe. Of course, Gian didn't play fair, and the board is now in a very strange state. The number of marks for each player might not be what you'd expect from a normal game. With Gian about to claim victory, Nobita starts to cry for help.
From his pocket, Doraemon pulls out a futuristic gadget: the "Double-Step Stopwatch!" This incredible device can bend time, allowing Nobita a single, golden opportunity: he gets to make two consecutive moves for 'O'. After Nobita uses his special double-move, the game ends immediately. If there are three 'O's in the same row, column, or diagonal of the board, Nobita wins.
You are Nobita's trusted friend, here to help him analyze the board. Doraemon guarantees that the board has at least two empty cells and that neither side has already won.
Given a 3x3 Tic-Tac-Toe board, you must help Nobita determine if it is possible to win after using the Double-Step Stopwatch. If Nobita can make two moves that result in an immediate win, show him the winning board. This means he gets to enjoy a victory feast of dorayaki! Otherwise, report that it is impossible to win.
If multiple winning moves exist, any of them is an acceptable answer.
The input will consist of an integer $$$t$$$ ($$$1 \le t \le 1,000$$$) on the first line, indicating the number of test cases. For each test case, there are 3 lines, each containing 3 characters, representing the Tic-Tac-Toe board.
3 X.X .O. ... O.X .O. X.. X.X .X. ...
YES X.X OOO ... YES O.X .O. XOO NO
In the first test case, Nobita places 'O' at cell (2,1) and (2,3), winning the game on the spot.
In the second test case, Nobita places 'O' at cell (3,2) and (3,3), winning the game on the spot.
You are given a rooted tree$$$^{\text{∗}}$$$ with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. The root is the vertex $$$1$$$.
A permutation$$$^{\text{†}}$$$ $$$p_1,p_2,\dots,p_n$$$ is good if and only if, for each $$$1 \le i \le n$$$, at least one of the following conditions is true:
Count the number of good permutations of length $$$n$$$, modulo $$$998\,244\,353$$$.
$$$^{\text{∗}}$$$A tree is a connected graph without cycles. A rooted tree is a tree where one vertex is special and called the root.
$$$^{\text{†}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).
$$$^{\text{‡}}$$$An ancestor of vertex $$$v$$$ is any vertex on the simple path from $$$v$$$ to the root, including the root, but not including $$$v$$$. The root has no ancestors.
$$$^{\text{§}}$$$A descendant of vertex $$$v$$$ is any vertex $$$u$$$ for which $$$v$$$ is an ancestor. No vertex is its own descendant.
The first line contains $$$t$$$ ($$$1 \le t \le 2\,500$$$) — the number of test cases.
The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 5\,000$$$) — the number of vertices.
The second line contains $$$n - 1$$$ integers $$$a_2, a_3, \ldots, a_n$$$ ($$$1 \le a_i \le i-1$$$) — $$$a_i$$$ represents the parent of the vertex $$$i$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\,000$$$.
For each test case, output one number — the number of good permutations modulo $$$998\,244\,353$$$.
5336713
3 6 20 75 237554682
In the first test case, the good permutations are $$$[1,2,3]$$$,$$$[2,1,3]$$$, and $$$[3,2,1]$$$.
In the second test case, all $$$3!=6$$$ permutations are good.
Nobita was tired of getting bullied by Gian. As he is a cultured citizen, he chose to solve this problem by planting $$$N$$$ mines in the school, which is a rectangular field of $$$R$$$ rows and $$$C$$$ columns. After he finished his business, he went back to his house and told Doraemon what he did. Doraemon was so proud of him, then asked if Nobita remembered where he put the mines. Unsurprisingly, he couldn't recall the location of any mine, and not even the number of mines he put in. Doraemon, however, expected this; he prepared a device that can locate every mine on the field. But the device requires the location of any mine in that field first.
Nobita was given a detector that receives a rectangular area and a positive integer $$$k$$$ that must be no greater than $$$20$$$. The detector will return the number of mines in that specified area modulo $$$k$$$.
Since Nobita needs to finish this fast for some reason, he can use this device not so many times before it is too late.
Your task is to help Nobita locate any mine (one mine) in the field using the detector no more than $$$69$$$ times.
Each test contains multiple test cases. The first line contains the number of test cases t ($$$1 \leq t \leq 100$$$).
For each test case, the first line contains 2 integers $$$R$$$, $$$C$$$ ($$$1 \leq R, C \leq 10^{9}$$$) — the number of rows and columns of the field.
The number of mines (i.e. $$$N$$$) in each test case is at least $$$1$$$ and at most $$$10^6$$$. Note that the number of mines is not provided.
It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$10^6$$$.
To use the detector, you should print a new line in the following format: "? $$$k$$$ $$$r_1$$$ $$$c_1$$$ $$$r_2$$$ $$$c_2$$$" ($$$1 \leq k \leq 20, 1 \leq r_1 \leq r_2 \leq R, 1 \leq c_1 \leq c_2 \leq C$$$).
As a response, the detector will return the amount of mines which are located at row $$$i$$$ column $$$j$$$ in that rectangle ($$$r_1 \leq i \leq r_2$$$, $$$c_1 \leq j \leq c_2$$$) modulo $$$k$$$.
To report the answer, you should print a new line in the following format: "! $$$r$$$ $$$c$$$" indicating that there is a mine located at row $$$r$$$ column $$$c$$$.
If you use the detector more than $$$69$$$ times, you ask a malformed query, or your answer is wrong, you will get Wrong answer.
After printing a query, do not forget to output the end of line and flush the output. To do this, use:
Note that the interactor is not adaptive, which means that the hidden arrays do not depend on the queries you make.
2 7 6 1 0 10 10 1
? 3 1 1 3 3 ? 2 5 1 5 6 ! 2 3 ? 2 1 5 8 9 ! 4 9
In the first testcase, the field has 7 rows and 6 columns. Suppose that the mines are located in $$$(2, 3), (5, 3), (5, 6)$$$.
In the second testcase, the field has $$$10$$$ rows and $$$10$$$ columns. Suppose there is only one mine located in $$$(4, 9)$$$.
Nobita has once again forgotten his homework. This time, Ajarn Nat asked him to design a special grid. Luckily, Doraemon pulls out a grid-maker-from-anywhere gadget that instantly creates such a grid.
The rules of the grid-maker-from-anywhere are as follows:
After the grid is built, Ajarn Nat provides Nobita with another sequence $$$x$$$ of length $$$n$$$. For each row $$$i$$$ of the grid, the gadget aligns $$$x$$$ with that row and computes the value $$$ y_i = \sum\limits_{j=1}^{n} f(i,j)\cdot x_j $$$
Collecting all $$$y_i$$$ for all $$$1 \le i \le n$$$ forms a new sequence $$$y$$$ of length $$$n$$$. Nobita must report this sequence $$$y$$$ to finally complete his homework.
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \leq a_i \lt 100$$$).
The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$0 \leq b_i \lt 100$$$).
The fourth line contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$0 \leq x_i \lt 100$$$).
It is guaranteed that $$$a_1 = b_1$$$.
A single line consists of $$$n$$$ integers — the sequence $$$y$$$.
41 3 5 71 2 4 81 4 1 2
29 17 22 32
From $$$a = [1, 3, 5, 7]$$$ and $$$b = [1, 2, 4, 8]$$$, the gadget constructs the following grid.
| $$$1$$$ | $$$2$$$ | $$$4$$$ | $$$8$$$ |
| $$$3$$$ | $$$1$$$ | $$$2$$$ | $$$4$$$ |
| $$$5$$$ | $$$3$$$ | $$$1$$$ | $$$2$$$ |
| $$$7$$$ | $$$5$$$ | $$$3$$$ | $$$1$$$ |
The sequence is $$$x=[1,4,1,2]$$$.