Codeforces Round 1135 (Div. 2)
A. Composite Permutation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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$$$).

Output

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.

Example
Input
3
1
4
5
Output
-1
4 3 2 1
4 5 3 1 2
Note

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.

B. Diverse String
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$.

Input

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$$$.

Output

For each test case, output a line with a single integer — the maximum possible diversity of the string after toggling at most $$$k$$$ characters.

Example
Input
4
1 1
0
4 4
1001
5 1
11111
7 2
1101001
Output
2
11
16
23
Note

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$$$.

C. Max Substitution
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$.

Input

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$$$.

Output

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$$$.

Example
Input
5
3
2 2 1
2
1000000000 1
4
6 7 2 2
3
3 4 2
1
1
Output
1
1000000000
32
9
1
Note

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$$$.

D. Reverse Partition
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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:

  • $$$c_1$$$ is the sum of the first $$$p_1$$$ elements of $$$b$$$,
  • $$$c_2$$$ is the sum of the next $$$p_2$$$ elements of $$$b$$$,

    ...

  • $$$c_m$$$ is the sum of the last $$$p_m$$$ elements of $$$b$$$.

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.

Input

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$$$.

Output

For each query, output a single integer — the number of special partitions of $$$a$$$ for the query, modulo $$$10^9 + 7$$$.

Example
Input
2
5 2 3
1 2 3 2 1
3 0
2 1
5 -1
8 3 6
3 1 4 5 1 7 2 3
1 0
4 2
8 -2
2 1
5 -1
7 3
Output
4
2
0
3
1
0
6
1
1
Note

In the first test case there are $$$3$$$ queries:

  • In the first query, the array is $$$a=[1,2,3,2,1]$$$. The special partitions are $$$[1,4],[2,3],[3,2]$$$, and $$$[4,1]$$$.
  • In the second query, the array is $$$a=[1,3,3,2,1]$$$. The special partitions are $$$[1,4]$$$, and $$$[4,1]$$$.
  • In the third query, the array is $$$a=[1,2,3,2,0]$$$. It can be shown that there are no special partitions.

E. Arithmetic Subarray
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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$$$.

Input

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$$$.

Output

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$$$.

Example
Input
4
5 1
1 2 6 4 5
5 1
1 2 3 100 200
3 1
1 1000000000 2
6 2
1 2 4 8 16 32
Output
5
4
3
4
Note

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]$$$.

F. Mooclear Reactor 3
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$:

  1. If atom $$$u_i$$$ and atom $$$v_i$$$ are in different moolecules, Bessie combines the moolecules into one moolecule containing the atoms from both.
  2. If the newly combined moolecule contains at least one reactive pair of atoms, it instantly explodes into single-atom moolecules.

After each experiment, Bessie wants to know the number of moolecules in her laboratory. Help her compute this count after every experiment!

Input

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$$$.

Output

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.

Example
Input
2
5 2 5
1 3
2 4
1 2
3 4
1 4
1 3
2 5
4 0 4
1 2
3 4
2 4
1 2
Output
4
3
5
5
4
3
2
1
1
Note

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$$$.