You are given two arrays $$$a_1, a_2, \ldots, a_n$$$ and $$$b_1, b_2, \ldots, b_n$$$.
In one operation, you can choose any integer $$$i$$$ from $$$1$$$ to $$$n$$$ and swap the numbers $$$a_i$$$ and $$$b_i$$$.
Determine whether, after using any (possibly zero) number of operations, the following two conditions can be satisfied simultaneously:
- $$$a_n = \max(a_1, a_2, \ldots, a_n)$$$,
- $$$b_n = \max(b_1, b_2, \ldots, b_n)$$$.
Here $$$\max(c_1, c_2, \ldots, c_k)$$$ denotes the maximum number among $$$c_1, c_2, \ldots, c_k$$$. For example, $$$\max(3, 5, 4) = 5$$$, $$$\max(1, 7, 7) = 7$$$, $$$\max(6, 2) = 6$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 200$$$). The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the length of the arrays.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 100$$$) — elements of the first array.
The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 100$$$) — elements of the second array.
For each test case, print "Yes" if after using any (possibly zero) number of operations the conditions described above are satisfied. Otherwise, print "No".
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
737 9 77 6 9410 10 15 1510 16 15 152100 9999 10011191 2 3 4 5 6 7 8 99 9 9 9 9 9 6 6 671 1 2 2 1 1 21 2 1 2 1 2 1230 45 30
Yes No Yes Yes Yes No No
In the first test case, you can swap the numbers $$$a_3$$$ and $$$b_3$$$, after which the array $$$a$$$ becomes equal to $$$[7, 9, 9]$$$, and the array $$$b$$$ becomes equal to $$$[7, 6, 7]$$$, and both conditions are met.
In the second test case, it can be proved that it is impossible to satisfy both conditions.
In the third test case, you can swap the numbers $$$a_1$$$ and $$$b_1$$$, after which the array $$$a$$$ becomes equal to $$$[99, 99]$$$, and the array $$$b$$$ becomes equal to $$$[100, 100]$$$, and both conditions are satisfied.
In fifth test case, you can swap $$$a_7$$$ and $$$b_7$$$, $$$a_8$$$ and $$$b_8$$$, $$$a_9$$$ and $$$b_9$$$, after which the array $$$a$$$ becomes equal to $$$[1, 2, 3, 4, 5, 6, 6, 6, 6]$$$, and the array $$$b$$$ becomes equal to $$$[9, 9, 9, 9, 9, 9, 7, 8, 9]$$$, and both conditions are satisfied.
Lottery "Three Sevens" was held for $$$m$$$ days. On day $$$i$$$, $$$n_i$$$ people with the numbers $$$a_{i, 1}, \ldots, a_{i, n_i}$$$ participated in the lottery.
It is known that in each of the $$$m$$$ days, only one winner was selected from the lottery participants. The lottery winner on day $$$i$$$ was not allowed to participate in the lottery in the days from $$$i+1$$$ to $$$m$$$.
Unfortunately, the information about the lottery winners has been lost. You need to find any possible list of lottery winners on days from $$$1$$$ to $$$m$$$ or determine that no solution exists.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 50\,000$$$). The description of the test cases follows.
The first line of each test case contains a single integer $$$m$$$ ($$$1 \le m \le 50\,000$$$) — the number of days in which the lottery was held.
Next, for each $$$i$$$ from $$$1$$$ to $$$m$$$, follows a two-line block of data.
The first line of each block contains a single integer $$$n_i$$$ ($$$1 \le n_i \le 50\,000$$$) — the number of lottery participants on day $$$i$$$.
The second line of the block contains integers $$$a_{i, 1}, \ldots, a_{i, n_i}$$$ ($$$1 \le a_{i, j} \le 50\,000$$$) — lottery participants on day $$$i$$$. It is guaranteed that all the numbers $$$a_{i, 1}, \ldots, a_{i, n_i}$$$ are pairwise distinct.
It is guaranteed that the sum of $$$n_i$$$ over all blocks of all test cases does not exceed $$$50\,000$$$.
For each test case, if there is no solution, print a single integer $$$-1$$$.
Otherwise, print $$$m$$$ integers $$$p_1, p_2, \ldots, p_m$$$ ($$$1 \le p_i \le 50\,000$$$) — lottery winners on days from $$$1$$$ to $$$m$$$. If there are multiple solutions, print any of them.
3341 2 4 832 9 121 4221 222 1441 2 3 4111413
8 2 1 -1 2 1 4 3
In the first test case, one of the answers is $$$[8, 2, 1]$$$ since the participant with the number $$$8$$$ participated on day $$$1$$$, but did not participate on days $$$2$$$ and $$$3$$$; the participant with the number $$$2$$$ participated on day $$$2$$$, but did not participate on day $$$3$$$; and the participant with the number $$$1$$$ participated on day $$$3$$$. Note that this is not the only possible answer, for example, $$$[8, 9, 4]$$$ is also a correct answer.
In the second test case, both lottery participants participated on both days, so any possible lottery winner on the day $$$1$$$ must have participated on the day $$$2$$$, which is not allowed. Thus, there is no correct answer.
In the third test case, only one participant participated on days $$$2$$$, $$$3$$$, $$$4$$$, and on day $$$1$$$ there is only one participant who did not participate in the lottery on days $$$2, 3, 4$$$ — participant $$$2$$$, which means $$$[2, 1, 4, 3]$$$ is the only correct answer to this test case.
The store sells $$$n$$$ types of candies with numbers from $$$1$$$ to $$$n$$$. One candy of type $$$i$$$ costs $$$b_i$$$ coins. In total, there are $$$a_i$$$ candies of type $$$i$$$ in the store.
You need to pack all available candies in packs, each pack should contain only one type of candies. Formally, for each type of candy $$$i$$$ you need to choose the integer $$$d_i$$$, denoting the number of type $$$i$$$ candies in one pack, so that $$$a_i$$$ is divided without remainder by $$$d_i$$$.
Then the cost of one pack of candies of type $$$i$$$ will be equal to $$$b_i \cdot d_i$$$. Let's denote this cost by $$$c_i$$$, that is, $$$c_i = b_i \cdot d_i$$$.
After packaging, packs will be placed on the shelf. Consider the cost of the packs placed on the shelf, in order $$$c_1, c_2, \ldots, c_n$$$. Price tags will be used to describe costs of the packs. One price tag can describe the cost of all packs from $$$l$$$ to $$$r$$$ inclusive if $$$c_l = c_{l+1} = \ldots = c_r$$$. Each of the packs from $$$1$$$ to $$$n$$$ must be described by at least one price tag. For example, if $$$c_1, \ldots, c_n = [4, 4, 2, 4, 4]$$$, to describe all the packs, a $$$3$$$ price tags will be enough, the first price tag describes the packs $$$1, 2$$$, the second: $$$3$$$, the third: $$$4, 5$$$.
You are given the integers $$$a_1, b_1, a_2, b_2, \ldots, a_n, b_n$$$. Your task is to choose integers $$$d_i$$$ so that $$$a_i$$$ is divisible by $$$d_i$$$ for all $$$i$$$, and the required number of price tags to describe the values of $$$c_1, c_2, \ldots, c_n$$$ is the minimum possible.
For a better understanding of the statement, look at the illustration of the first test case of the first test:
Let's repeat the meaning of the notation used in the problem:
$$$a_i$$$ — the number of candies of type $$$i$$$ available in the store.
$$$b_i$$$ — the cost of one candy of type $$$i$$$.
$$$d_i$$$ — the number of candies of type $$$i$$$ in one pack.
$$$c_i$$$ — the cost of one pack of candies of type $$$i$$$ is expressed by the formula $$$c_i = b_i \cdot d_i$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100\,000$$$). Description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 200\,000$$$) — the number of types of candies.
Each of the next $$$n$$$ lines of each test case contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i \le 10^9$$$, $$$1 \le b_i \le 10\,000$$$) — the number of candies and the cost of one candy of type $$$i$$$, respectively.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$200\,000$$$.
For each test case, output the minimum number of price tags required to describe the costs of all packs of candies in the store.
5420 36 214 520 73444 52002 102020 257 76 515 210 37 7510 111 55 12 28 267 1212 35 39 129 31000000000 10000
2 1 3 2 5
In the first test case, you can choose $$$d_1 = 4$$$, $$$d_2 = 6$$$, $$$d_3 = 7$$$, $$$d_4 = 5$$$. Then the cost of packs will be equal to $$$[12, 12, 35, 35]$$$. $$$2$$$ price tags are enough to describe them, the first price tag for $$$c_1, c_2$$$ and the second price tag for $$$c_3, c_4$$$. It can be shown that with any correct choice of $$$d_i$$$, at least $$$2$$$ of the price tag will be needed to describe all the packs. Also note that this example is illustrated by a picture in the statement.
In the second test case, with $$$d_1 = 4$$$, $$$d_2 = 2$$$, $$$d_3 = 10$$$, the costs of all packs will be equal to $$$20$$$. Thus, $$$1$$$ price tag is enough to describe all the packs. Note that $$$a_i$$$ is divisible by $$$d_i$$$ for all $$$i$$$, which is necessary condition.
In the third test case, it is not difficult to understand that one price tag can be used to describe $$$2$$$nd, $$$3$$$rd and $$$4$$$th packs. And additionally a price tag for pack $$$1$$$ and pack $$$5$$$. Total: $$$3$$$ price tags.
You are given an array $$$a_1, a_2, \ldots, a_n$$$ consisting of integers such that $$$a_1 + a_2 + \ldots + a_n = 0$$$.
You have to rearrange the elements of the array $$$a$$$ so that the following condition is satisfied:
$$$$$$\max\limits_{1 \le l \le r \le n} \lvert a_l + a_{l+1} + \ldots + a_r \rvert \lt \max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n),$$$$$$ where $$$|x|$$$ denotes the absolute value of $$$x$$$.
More formally, determine if there exists a permutation $$$p_1, p_2, \ldots, p_n$$$ that for the array $$$a_{p_1}, a_{p_2}, \ldots, a_{p_n}$$$, the condition above is satisfied, and find the corresponding array.
Recall that the array $$$p_1, p_2, \ldots, p_n$$$ is called a permutation if for each integer $$$x$$$ from $$$1$$$ to $$$n$$$ there is exactly one $$$i$$$ from $$$1$$$ to $$$n$$$ such that $$$p_i = x$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 50\,000$$$). The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 300\,000$$$) — the length of the array $$$a$$$.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — elements of the array $$$a$$$. It is guaranteed that the sum of the array $$$a$$$ is zero, in other words: $$$a_1 + a_2 + \ldots + a_n = 0$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$300\,000$$$.
For each test case, if it is impossible to rearrange the elements of the array $$$a$$$ in the required way, print "No" in a single line.
If possible, print "Yes" in the first line, and then in a separate line $$$n$$$ numbers — elements $$$a_1, a_2, \ldots, a_n$$$ rearranged in a valid order ($$$a_{p_1}, a_{p_2}, \ldots, a_{p_n}$$$).
If there are several possible answers, you can output any of them.
7 4 3 4 -2 -5 5 2 2 2 -3 -3 8 -3 -3 1 1 1 1 1 1 3 0 1 -1 7 -3 4 3 4 -4 -4 0 1 0 7 -18 13 -18 -17 12 15 13
Yes -5 -2 3 4 Yes -3 2 -3 2 2 Yes 1 1 1 -3 1 1 1 -3 Yes -1 0 1 Yes 4 -4 4 -4 0 3 -3 No Yes 13 12 -18 15 -18 13 -17
In the first test case $$$\max(a_1, \ldots, a_n) - \min(a_1, \ldots, a_n) = 9$$$. Therefore, the elements can be rearranged as $$$[-5, -2, 3, 4]$$$. It is easy to see that for such an arrangement $$$\lvert a_l + \ldots + a_r \rvert$$$ is always not greater than $$$7$$$, and therefore less than $$$9$$$.
In the second test case you can rearrange the elements of the array as $$$[-3, 2, -3, 2, 2]$$$. Then the maximum modulus of the sum will be reached on the subarray $$$[-3, 2, -3]$$$, and will be equal to $$$\lvert -3 + 2 + -3 \rvert = \lvert -4 \rvert = 4$$$, which is less than $$$5$$$.
In the fourth test example, any rearrangement of the array $$$a$$$ will be suitable as an answer, including $$$[-1, 0, 1]$$$.
Let's call an array $$$b_1, b_2, \ldots, b_m$$$ a test if $$$b_1 = m - 1$$$.
Let's call an array $$$b_1, b_2, \ldots, b_m$$$ a multitest if the array $$$b_2, b_3, \ldots, b_m$$$ can be split into $$$b_1$$$ non-empty subarrays so that each of these subarrays is a test. Note that each element of the array must be included in exactly one subarray, and the subarrays must consist of consecutive elements.
Let's define the function $$$f$$$ from the array $$$b_1, b_2, \ldots, b_m$$$ as the minimum number of operations of the form "Replace any $$$b_i$$$ with any non-negative integer $$$x$$$", which needs to be done so that the array $$$b_1, b_2, \ldots, b_m$$$ becomes a multitest.
You are given an array of positive integers $$$a_1, a_2, \ldots, a_n$$$. For each $$$i$$$ from $$$1$$$ to $$$n - 1$$$, find $$$f([a_i, a_{i+1}, \ldots, a_n])$$$.
Below are some examples of tests and multitests.
- Tests: $$$[\underline{1}, 5]$$$, $$$[\underline{2}, 2, 2]$$$, $$$[\underline{3}, 4, 1, 1]$$$, $$$[\underline{5}, 0, 0, 0, 0, 0]$$$, $$$[\underline{7}, 1, 2, 3, 4, 5, 6, 7]$$$, $$$[\underline{0}]$$$. These arrays are tests since their first element (underlined) is equal to the length of the array minus one.
- Multitests: $$$[1, \underline{\underline{1}, 1}]$$$, $$$[2, \underline{\underline{3}, 0, 0, 1}, \underline{\underline{1}, 12}]$$$, $$$[3, \underline{\underline{2}, 2, 7}, \underline{\underline{1}, 1}, \underline{\underline{3}, 4, 4, 4}]$$$, $$$[4, \underline{\underline{0}}, \underline{\underline{3}, 1, 7, 9}, \underline{\underline{4}, 2, 0, 0, 9}, \underline{\underline{1}, 777}]$$$. Underlined are the subarrays after the split, and double underlined are the first elements of each subarray.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 300\,000$$$). The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 300\,000$$$) — the length of the array $$$a$$$.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 300\,000$$$) — elements of the array $$$a$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$300\,000$$$.
For each test case print $$$n - 1$$$ numbers — $$$f([a_i, a_{i+1}, \ldots, a_n])$$$ for each $$$i$$$ from $$$1$$$ to $$$n - 1$$$.
341 2 1 773 1 3 1 2 1 142 7 1 1
0 1 1 0 1 1 0 1 1 1 1 1
1193 4 1 2 1 7 7 3 1 3 1 2 1 1 4 2 7 1 1
0 0 1 1 1 1 1 1 1 0 1 0 1 0 2 1 1 1
In the first test case of the first test the array $$$[1, 2, 1, 7]$$$ is a multitest since the array $$$[2, 1, 7]$$$ is a test. The array $$$[2, 1, 7]$$$ is not a multitest, but after replacing the first number with $$$1$$$, an array $$$[1, 1, 7]$$$ is obtained, which is a multitest. The array $$$[1, 7]$$$ is also not a multitest, but the array $$$[1, 0]$$$ is, so $$$f([1, 7]) = 1$$$.
In the second test case of first test, for $$$i = 2$$$, $$$f([a_i, a_{i+1}, \ldots, a_n]) = f([1, 3, 1, 2, 1, 1]) = 1$$$, since the array itself is not a multitest, but after replacing the second element with $$$4$$$ you get multitest.
In the third test case of first test, for $$$i = 1$$$, $$$f([a_i, a_{i+1}, \ldots, a_n]) = f([2, 7, 1, 1]) = 1$$$, since the array itself is not a multitest, but after replacing the second element with $$$0$$$ you get multitest.
The second test is an array composed of all the numbers of the first test. Therefore $$$f([a_1, a_2, \ldots, a_n])$$$ naturally equals to $$$0$$$.
Grandfather Ahmed's School has $$$n+1$$$ students. The students are divided into $$$k$$$ classes, and $$$s_i$$$ students study in the $$$i$$$-th class. So, $$$s_1 + s_2 + \ldots + s_k = n+1$$$.
Due to the upcoming April Fools' Day, all students will receive gifts!
Grandfather Ahmed planned to order $$$n+1$$$ boxes of gifts. Each box can contain one or more gifts. He plans to distribute the boxes between classes so that the following conditions are satisfied:
- Class number $$$i$$$ receives exactly $$$s_i$$$ boxes (so that each student can open exactly one box).
- The total number of gifts in the boxes received by the $$$i$$$-th class should be a multiple of $$$s_i$$$ (it should be possible to equally distribute the gifts among the $$$s_i$$$ students of this class).
Unfortunately, Grandfather Ahmed ordered only $$$n$$$ boxes with gifts, the $$$i$$$-th of which contains $$$a_i$$$ gifts.
Ahmed has to buy the missing gift box, and the number of gifts in the box should be an integer between $$$1$$$ and $$$10^6$$$. Help Ahmed to determine, how many gifts should the missing box contain, and build a suitable distribution of boxes to classes, or report that this is impossible.
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 200$$$, $$$k \le n + 1$$$).
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the number of gifts in the available boxes.
The third line contains $$$k$$$ integers $$$s_1, s_2, \ldots, s_k$$$ ($$$1 \le s_i \le n+1$$$) — the number of students in classes. It is guaranteed that $$$\sum s_i = n+1$$$.
If there is no way to buy the remaining box, output the integer $$$-1$$$ in a single line.
Otherwise, in the first line, output a single integer $$$s$$$ — the number of gifts in the box that Grandfather Ahmed should buy ($$$1 \le s \le 10^6$$$).
Next, in $$$k$$$ lines, print the distribution of boxes to classes. In the $$$i$$$-th line print $$$s_i$$$ integers — the sizes of the boxes that should be sent to the $$$i$$$-th class.
If there are multiple solutions, print any of them.
4 2 7 7 7 127 2 3
1 7 7 7 127 1
18 4 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 6 1 9 3
9 7 1 7 6 5 4 9 1 2 3 8 3 2 9 8 9 6 5 4
In the first test, Grandfather Ahmed can buy a box with just $$$1$$$ gift. After that, two boxes with $$$7$$$ gifts are sent to the first class. $$$7 + 7 = 14$$$ is divisible by $$$2$$$. And the second class gets boxes with $$$1, 7, 127$$$ gifts. $$$1 + 7 + 127 = 135$$$ is evenly divisible by $$$3$$$.
In the second test, the classes have sizes $$$6$$$, $$$1$$$, $$$9$$$, and $$$3$$$. We show that the available boxes are enough to distribute into classes with sizes $$$6$$$, $$$9$$$, $$$3$$$, and in the class with size $$$1$$$, you can buy a box of any size. In class with size $$$6$$$ we send boxes with sizes $$$7$$$, $$$1$$$, $$$7$$$, $$$6$$$, $$$5$$$, $$$4$$$. $$$7 + 1 + 7 + 6 + 5 + 4 = 30$$$ is divisible by $$$6$$$. In class with size $$$9$$$ we send boxes with sizes $$$1$$$, $$$2$$$, $$$3$$$, $$$8$$$, $$$3$$$, $$$2$$$, $$$9$$$, $$$8$$$, $$$9$$$. $$$1 + 2 + 3 + 8 + 3 + 2 + 9 + 8 + 9 = 45$$$ is divisible by $$$9$$$. The remaining boxes ($$$6$$$, $$$5$$$, $$$4$$$) are sent to the class with size $$$3$$$. $$$6 + 5 + 4 = 15$$$ is divisible by $$$3$$$.