You are given an integer $$$n$$$. Construct a permutation$$$^{\text{∗}}$$$ $$$p$$$ of length $$$n$$$ such that $$$i \cdot p_i$$$ is composite$$$^{\text{†}}$$$ for every $$$1 \le i \le n$$$, or determine that no such permutation exists.
$$$^{\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{†}}$$$A positive integer $$$x$$$ is composite if it has at least one other divisor besides $$$1$$$ and $$$x$$$. For example, $$$6$$$ is composite because $$$2$$$ is a divisor of it, while $$$1$$$ and $$$5$$$ are not.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.
The only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$).
For each test case, if no suitable permutation exists, print a single integer $$$-1$$$.
Otherwise, print $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ representing a suitable permutation.
If there are multiple solutions, print any of them.
3145
-14 3 2 14 5 3 1 2
In the first test case, it can be shown that no suitable permutation exists.
In the second test case, the values of $$$i\cdot p_i$$$ are $$$4$$$, $$$6$$$, $$$6$$$, and $$$4$$$, respectively, which are all composite.
The diversity of a binary string $$$s$$$ is the number of distinct$$$^{\text{∗}}$$$ strings that can be obtained by performing the following operation at most once:
Choose an integer $$$0 \leq x \leq 1$$$ and two integers $$$1 \leq l \leq r \leq n$$$, and set $$$s_i := x$$$ for all $$$l \leq i \leq r$$$.
For example, the string 10 has diversity $$$3$$$ because the strings 10, 11, and 00. can be obtained.
You are given a string $$$s$$$ of length $$$n$$$ as well as an integer $$$k$$$. You are allowed to toggle the values of at most $$$k$$$ characters in the string. Your task is to determine the maximum possible diversity of the resulting string.
$$$^{\text{∗}}$$$Two strings $$$a$$$ and $$$b$$$ are distinct if there exists an index $$$i$$$ such that $$$a_i \neq b_i$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq k \leq n$$$) — the length of the string and the maximum number of characters you are allowed to toggle.
The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.
For each test case, output a line with a single integer — the maximum possible diversity of the string after toggling at most $$$k$$$ characters.
41 104 410015 1111117 21101001
2111623
In the first test case, it is optimal to toggle the first character, resulting in the string 1 with a diversity of $$$2$$$.
In the second test case, the string 1111 achieves the maximum possible diversity of $$$11$$$.
You are given an array $$$a$$$ of length $$$n$$$. In one operation, you may replace the unique largest element in $$$a$$$ with any strictly smaller positive integer (i.e., any integer $$$x$$$ such that $$$1 \le x \lt \max(a)$$$). You can only perform this operation if $$$a$$$ has a unique largest element.
Determine the number of distinct$$$^{\text{∗}}$$$ arrays that can be obtained by performing the operation any number of times (possibly zero). Since the answer may be large, output it modulo $$$10^9+7$$$.
$$$^{\text{∗}}$$$Two arrays $$$a$$$ and $$$b$$$ are considered distinct if they differ in at least one position, i.e., there exists an index $$$i$$$ such that $$$a_i \ne b_i$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array.
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 elements of the array.
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 line with a single integer — the number of distinct arrays that can be obtained by performing the operation any number of times, modulo $$$10^9+7$$$.
532 2 121000000000 146 7 2 233 4 211
110000000003291
In the first test case, since the maximum element $$$2$$$ is not unique, the only array that can be obtained is $$$[2,2,1]$$$ — the initial array.
In the second test case, the maximum element is $$$1\,000\,000\,000$$$. It can be shown that after any number of operations, the possible arrays are $$$[1,1], [2,1], [3,1], \ldots [1\,000\,000\,000,1]$$$. Hence the answer is $$$1\,000\,000\,000$$$.
You are given positive integers $$$n$$$ and $$$m$$$.
A partition is an array $$$p$$$ of $$$m$$$ positive integers such that $$$p_1 + p_2 + \ldots + p_m = n.$$$
For any array $$$b$$$ of length $$$n$$$ and a partition $$$p$$$, define $$$f(b, p)$$$ as an array $$$c$$$ of length $$$m$$$ where:
...
For an array $$$d$$$ of length $$$n$$$, let $$$e$$$ be the array obtained by reversing $$$d$$$. A partition $$$p$$$ is a special partition of $$$d$$$ if $$$f(d, p) = f(e, p)$$$.
You are given an array $$$a$$$ of length $$$n$$$. You must answer $$$q$$$ independent queries. For each query, you are given two integers $$$i$$$ and $$$v$$$. Set $$$a_i := a_i + v$$$, and then output the number of special partitions of $$$a$$$. Since the answer may be large, output it modulo $$$10^9 + 7$$$.
Note that the queries are independent, meaning that after each query, $$$a$$$ reverts to its original value.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$1 \le m \le n \le 2 \cdot 10^5, 1 \le q \le 2 \cdot 10^5$$$) – the length of $$$a$$$, the length of the partition, and the number of queries respectively.
The second line of each test case contains $$$n$$$ integers – $$$a_1, a_2, \ldots, a_n$$$ ($$$|a_i| \le 10^9$$$).
The next $$$q$$$ lines of each test case contain two integers $$$i$$$ and $$$v$$$ ($$$1 \le i \le n, |v| \le 10^9$$$).
It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$.
For each query, output a single integer — the number of special partitions of $$$a$$$ for the query, modulo $$$10^9 + 7$$$.
25 2 31 2 3 2 13 02 15 -18 3 63 1 4 5 1 7 2 31 04 28 -22 15 -17 3
420310611
In the first test case there are $$$3$$$ queries:
You are given an array $$$a$$$ of length $$$n$$$ and a positive integer $$$k$$$.
A subarray$$$^{\text{∗}}$$$ $$$a[l..r]$$$ is called an arithmetic subarray if the difference between consecutive elements is constant; that is, $$$$$$a_{l+1} - a_l = a_{l+2} - a_{l+1} = \ldots = a_r - a_{r-1}.$$$$$$ Note that all subarrays of length one are arithmetic.
You are allowed to choose at most $$$k$$$ elements of $$$a$$$ and change them to any integers (not necessarily in $$$[1,10^9]$$$) of your choice. Your task is to find the maximum possible length of an arithmetic subarray of $$$a$$$ after these changes.
$$$^{\text{∗}}$$$A subarray of $$$a$$$ is the array $$$[a_l,a_{l+1},\ldots a_r]$$$ for some $$$1\le l\le r\le n$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le \min(n, 1500)$$$).
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i \le 10^9$$$).
It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2\cdot 10^5$$$. It is guaranteed that the sum of $$$n\cdot k$$$ across all test cases does not exceed $$$10^7$$$.
For each test case, output a single integer — the maximum possible length of an arithmetic subarray of $$$a$$$ after changing at most $$$k$$$ elements of $$$a$$$.
45 11 2 6 4 55 11 2 3 100 2003 11 1000000000 26 21 2 4 8 16 32
5434
In the first test case, the answer of $$$5$$$ can be achieved by $$$a=[1,2,3,4,5]$$$.
In the third test case, the answer of $$$3$$$ can be achieved by $$$a=[1\,999\,999\,998,1\,000\,000\,000,2]$$$.
Bessie is trying to develop energy-efficient moolecules for her mooclear reactor!
She has $$$n$$$ individual atoms, numbered from $$$1$$$ to $$$n$$$. Initially, each atom forms its own single-atom moolecule.
There are $$$m$$$ reactive pairs of atoms. If a reactive pair of atoms ever ends up in the same moolecule, the moolecule becomes unstable and immediately explodes. After the explosion, all atoms in the moolecule separate into single-atom moolecules.
Bessie performs $$$q$$$ experiments in her lab. In the $$$i$$$-th experiment, she attempts to merge the moolecule containing atom $$$u_i$$$ with the moolecule containing atom $$$v_i$$$:
After each experiment, Bessie wants to know the number of moolecules in her laboratory. Help her compute this count after every experiment!
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$2 \le n \le 2\cdot 10^5$$$, $$$0 \le m \le 2\cdot 10^5$$$, $$$1 \le q \le 2\cdot 10^5$$$) — the number of atoms, the number of reactive pairs, and the number of experiments, respectively.
Each of the next $$$m$$$ lines contains two integers $$$x_j$$$ and $$$y_j$$$ ($$$1 \le x_j, y_j \le n$$$, $$$x_j \neq y_j$$$), denoting that atoms $$$x_j$$$ and $$$y_j$$$ are a reactive pair. It is guaranteed that $$$(x_i,y_i)\ne (x_j,y_j)$$$ and $$$(x_i,y_i)\ne (y_j,x_j)$$$ for all $$$1\le i \lt j\le m$$$.
Each of the next $$$q$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$), denoting the atoms Bessie attempts to merge in the $$$i$$$-th experiment.
It is guaranteed that the sums of $$$n$$$, $$$m$$$, and $$$q$$$ over all test cases do not exceed $$$2\cdot 10^5$$$.
For each test case, print $$$q$$$ integers, each on a new line. The $$$i$$$-th integer should be the total number of moolecules after the $$$i$$$-th experiment.
25 2 51 32 41 23 41 41 32 54 0 41 23 42 41 2
435543211
In the first test case, there are two reactive pairs: $$$(1,3)$$$ and $$$(2,4)$$$.
In the first two experiments, Bessie successfully merges two moolecules, and the number of moolecules decreases by one each time.
The third and fourth experiments both cause explosions, causing the number of moolecules to return to $$$5$$$.
The fifth experiment is a successful merge, so the number of moolecules decreases to $$$4$$$.