apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given $$$n$$$ one-dimensional segments (each segment is denoted by two integers — its endpoints).

Let's define the function $$$f(x)$$$ as the number of segments covering point $$$x$$$ (a segment covers the point $$$x$$$ if $$$l \le x \le r$$$, where $$$l$$$ is the left endpoint and $$$r$$$ is the right endpoint of the segment).

An integer point $$$x$$$ is called ideal if it belongs to more segments than any other integer point, i. e. $$$f(y) < f(x)$$$ is true for any other integer point $$$y$$$.

You are given an integer $$$k$$$. Your task is to determine whether it is possible to remove some (possibly zero) segments, so that the given point $$$k$$$ becomes ideal.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 50$$$).

Then $$$n$$$ lines follow, $$$i$$$-th line of them contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i, r_i \le 50$$$; $$$l_i \le r_i$$$) — the endpoints of the $$$i$$$-th segment.

## Output Format
For each test case, print YES if it is possible to remove some (possibly zero) segments, so that the given point $$$k$$$ becomes ideal, otherwise print NO.

You may print each letter in any case (YES, yes, Yes will all be recognized as positive answer, NO, no and nO will all be recognized as negative answer).

## Examples
```input
4
4 3
1 3
7 9
2 5
3 6
2 9
1 4
3 7
1 3
2 4
3 5
1 4
6 7
5 5
```
```output
YES
NO
NO
YES
```

## Note
In the first example, the point $$$3$$$ is already ideal (it is covered by three segments), so you don't have to delete anything.

In the fourth example, you can delete everything except the segment $$$[5, 5]$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an undirected graph consisting of $$$n$$$ vertices and $$$n$$$ edges, where $$$n$$$ is divisible by $$$6$$$. Each edge has a weight, which is a positive (greater than zero) integer.

The graph has the following structure: it is split into $$$\frac{n}{3}$$$ triples of vertices, the first triple consisting of vertices $$$1, 2, 3$$$, the second triple consisting of vertices $$$4, 5, 6$$$, and so on. Every pair of vertices from the same triple is connected by an edge. There are no edges between vertices from different triples.

You have to paint the vertices of this graph into two colors, red and blue. Each vertex should have exactly one color, there should be exactly $$$\frac{n}{2}$$$ red vertices and $$$\frac{n}{2}$$$ blue vertices. The coloring is called valid if it meets these constraints.

The weight of the coloring is the sum of weights of edges connecting two vertices with different colors.

Let $$$W$$$ be the maximum possible weight of a valid coloring. Calculate the number of valid colorings with weight $$$W$$$, and print it modulo $$$998244353$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$6 \le n \le 3 \cdot 10^5$$$, $$$n$$$ is divisible by $$$6$$$).

The second line contains $$$n$$$ integers $$$w_1, w_2, \dots, w_n$$$ ($$$1 \le w_i \le 1000$$$) — the weights of the edges. Edge $$$1$$$ connects vertices $$$1$$$ and $$$2$$$, edge $$$2$$$ connects vertices $$$1$$$ and $$$3$$$, edge $$$3$$$ connects vertices $$$2$$$ and $$$3$$$, edge $$$4$$$ connects vertices $$$4$$$ and $$$5$$$, edge $$$5$$$ connects vertices $$$4$$$ and $$$6$$$, edge $$$6$$$ connects vertices $$$5$$$ and $$$6$$$, and so on.

## Output Format
Print one integer — the number of valid colorings with maximum possible weight, taken modulo $$$998244353$$$.

## Examples
```input
12
1 3 3 7 8 5 2 2 2 2 4 2
```
```output
36
```
-----
```input
6
4 2 6 6 6 4
```
```output
2
```

## Note
The following picture describes the graph from the first example test.

The maximum possible weight of a valid coloring of this graph is $$$31$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a_1, a_2, \ldots, a_n$$$ of positive integers.

You can make this operation multiple (possibly zero) times:

- Choose two indices $$$i$$$, $$$j$$$ ($$$1 \leq i, j \leq n$$$, $$$i \neq j$$$).
- Assign $$$a_i := \lceil \frac{a_i}{a_j} \rceil$$$. Here $$$\lceil x \rceil$$$ denotes $$$x$$$ rounded up to the smallest integer $$$\geq x$$$.

Is it possible to make all array elements equal by some sequence of operations (possibly empty)? If yes, print any way to do it in at most $$$30n$$$ operations.

It can be proven, that under the problem constraints, if some way exists to make all elements equal, there exists a way with at most $$$30n$$$ operations.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. Descriptions of test cases follow.

The first line of each test case description contains a single integer $$$n$$$ ($$$1 \leq n \leq 100$$$).

The second line of each test case description contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

It is guaranteed, that the sum of $$$n$$$ for all test cases does not exceed $$$1000$$$.

## Output Format
For each test case print a single integer $$$q$$$ ($$$-1 \leq q \leq 30n$$$). If $$$q=-1$$$, there is no solution, otherwise $$$q$$$ is equal to the number of operations.

If $$$q \geq 0$$$, on the next $$$q$$$ lines print two integers $$$i$$$, $$$j$$$ ($$$1 \leq i, j \leq n$$$, $$$i \neq j$$$) — descriptions of operations.

If there are multiple solutions, you can print any.

## Examples
```input
10
1
100
3
1 1 1
2
2 1
2
5 5
3
4 3 2
4
3 3 4 4
2
2 100
5
5 3 6 7 8
6
3 3 80 3 8 3
4
19 40 19 55
```
```output
0
0
-1
0
2
1 3
2 1
4
3 1
4 2
1 3
2 4
6
2 1
2 1
2 1
2 1
2 1
2 1
8
5 2
4 2
3 2
1 3
1 3
2 1
4 1
5 1
4
5 1
3 1
3 1
3 1
9
4 2
2 1
1 2
1 2
3 2
3 2
1 4
2 4
3 4
```

## Note
In the first and second, fourth test cases all numbers are equal, so it is possible to do nothing.

In the third test case, it is impossible to make all numbers equal.

In the fifth test case: $$$[\color{red}{4}, 3, \color{blue}{2}] \to [\color{blue}{2}, \color{red}{3}, 2] \to [2, 2, 2]$$$.

In the sixth test case: $$$[\color{blue}{3}, 3, \color{red}{4}, 4] \to [3, \color{blue}{3}, 2, \color{red}{4}] \to [\color{red}{3}, 3, \color{blue}{2}, 2] \to [2, \color{red}{3}, 2, \color{blue}{2}] \to [2, 2, 2, 2]$$$.

Here the red numbers are $$$i$$$ indices (that will be assigned), blue numbers are $$$j$$$ indices.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a string $$$s$$$. You can reorder the characters to form a string $$$t$$$. Define $$$t_{\mathrm{max}}$$$ to be the lexicographical maximum of $$$t$$$ and $$$t$$$ in reverse order.

Given $$$s$$$ determine the lexicographically minimum value of $$$t_{\mathrm{max}}$$$ over all reorderings $$$t$$$ of $$$s$$$.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases. Descriptions of test cases follow.

The first and only line of each test case contains a string $$$s$$$ ($$$1 \leq |s| \leq 10^5$$$). $$$s$$$ consists of only lowercase English letters.

It is guaranteed that the sum of $$$|s|$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case print the lexicographically minimum value of $$$t_{\mathrm{max}}$$$ over all reorderings $$$t$$$ of $$$s$$$.

## Examples
```input
12
a
aab
abb
abc
aabb
aabbb
aaabb
abbb
abbbb
abbcc
eaga
ffcaba
```
```output
a
aba
bab
bca
abba
abbba
ababa
bbab
bbabb
bbcca
agea
acffba
```

## Note
For the first test case, there is only one reordering of $$$s$$$, namely "a".

For the second test case, there are three reorderings of $$$s$$$.

- $$$t = \mathtt{aab}$$$: $$$t_{\mathrm{max}} = \max(\mathtt{aab}, \mathtt{baa}) = \mathtt{baa}$$$
- $$$t = \mathtt{aba}$$$: $$$t_{\mathrm{max}} = \max(\mathtt{aba}, \mathtt{aba}) = \mathtt{aba}$$$
- $$$t = \mathtt{baa}$$$: $$$t_{\mathrm{max}} = \max(\mathtt{baa}, \mathtt{aab}) = \mathtt{baa}$$$

The lexicographical minimum of $$$t_{\mathrm{max}}$$$ over all cases is "aba".

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
There are $$$n$$$ people that will participate in voting. Each person has exactly one vote.

$$$i$$$-th person has a team $$$t_i$$$ ($$$1 \leq t_i \leq n$$$) where $$$t_i = t_j$$$ means $$$i$$$, $$$j$$$ are in the same team. By the rules each person should vote for the person from the different team. Note that it automatically means that each person can't vote for himself.

Each person knows the number of votes $$$c_i$$$ he wants to get. How many possible votings exists, such that each person will get the desired number of votes? Due to this number can be big, find it by modulo $$$998\,244\,353$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 200$$$) — the number of people.

The second line contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$0 \leq c_i \leq n$$$) — desired number of votes. It is guaranteed, that $$$\sum\limits_{i=1}^{n} c_i = n$$$.

The third line contains $$$n$$$ integers $$$t_1, t_2, \ldots, t_n$$$ ($$$1 \leq t_i \leq n$$$) — team numbers.

## Output Format
Print a single integer — the number of possible votings by modulo $$$998\,244\,353$$$.

## Examples
```input
3
1 1 1
1 2 3
```
```output
2
```
-----
```input
5
2 0 1 0 2
1 2 3 4 5
```
```output
10
```
-----
```input
5
1 2 2 0 0
3 5 4 3 4
```
```output
5
```

## Note
In the first test there are two possible votings: $$$(2, 3, 1)$$$, $$$(3, 1, 2)$$$.

In the third test there are five possible votings: $$$(3, 3, 2, 2, 1)$$$, $$$(2, 3, 2, 3, 1)$$$, $$$(3, 3, 1, 2, 2)$$$, $$$(3, 1, 2, 3, 2)$$$, $$$(2, 3, 1, 3, 2)$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You are given a tree with $$$n$$$ vertices.

A hero $$$k$$$ times do the following operation:

- Choose some edge.
- Remove it.
- Take one of the two remaining parts and delete it.
- Write the number of vertices in the remaining part.

You are given an initial tree and the a sequence of written numbers. Find the number of ways to make operations such that the written numbers are equal to the given numbers. Due to the answer can be big, find it by modulo $$$998\,244\,353$$$. Two ways are considered different, if on some operation edge or remaining part are selected differently.

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 5000$$$) — the number of vertices.

Each of the next $$$n-1$$$ lines contains two integers $$$s$$$, $$$f$$$ ($$$1 \leq s, f \leq n$$$, $$$s \neq f$$$) — description of edge $$$(s, f)$$$.

Next line contains a single integer $$$k$$$ ($$$1 \leq k \leq \min{(6, n - 1)}$$$) — the number of operations.

Next line contains $$$k$$$ integers $$$s_1, s_2, \ldots, s_k$$$ ($$$n > s_1 > s_2 > \ldots > s_k \geq 1$$$) — written numbers.

## Output Format
Print a single integer — the answer to the problem by modulo $$$998\,244\,353$$$.

## Examples
```input
3
1 2
2 3
2
2 1
```
```output
4
```
-----
```input
7
2 1
3 2
4 1
5 3
6 4
7 4
2
4 2
```
```output
2
```
-----
```input
7
1 2
1 3
1 4
2 5
3 6
4 7
1
2
```
```output
3
```
-----
```input
7
1 2
1 3
1 4
2 5
3 6
4 7
4
6 5 2 1
```
```output
24
```
-----
```input
8
1 2
2 3
3 4
3 5
3 6
3 7
3 8
2
7 4
```
```output
0
```

## Note
In the first test there are four possible ways to make operations:

- Remove the edge $$$(1, 2)$$$ and delete vertex $$$1$$$. Remove the edge $$$(2, 3)$$$ and delete vertex $$$2$$$.
- Remove the edge $$$(1, 2)$$$ and delete vertex $$$1$$$. Remove the edge $$$(3, 2)$$$ and delete vertex $$$3$$$.
- Remove the edge $$$(3, 2)$$$ and delete vertex $$$3$$$. Remove the edge $$$(1, 2)$$$ and delete vertex $$$1$$$.
- Remove the edge $$$(3, 2)$$$ and delete vertex $$$3$$$. Remove the edge $$$(2, 1)$$$ and delete vertex $$$2$$$.

In the second test there are two possible ways to make operations:

- Remove the edge $$$(4, 1)$$$ and delete the part with vertex $$$4$$$. Remove the edge $$$(2, 3)$$$ and delete the part with vertex $$$2$$$.
- Remove the edge $$$(4, 1)$$$ and delete the part with vertex $$$4$$$. Remove the edge $$$(3, 2)$$$ and delete the part with vertex $$$3$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 1024.0 MB

# Problem
YunQian is standing on an infinite plane with the Cartesian coordinate system on it. In one move, she can move to the diagonally adjacent point on the top right or the adjacent point on the left.

That is, if she is standing on point $$$(x,y)$$$, she can either move to point $$$(x+1,y+1)$$$ or point $$$(x-1,y)$$$.

YunQian initially stands at point $$$(a,b)$$$ and wants to move to point $$$(c,d)$$$. Find the minimum number of moves she needs to make or declare that it is impossible.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases. The description of test cases follows.

The first line and only line of each test case contain four integers $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ ($$$-10^8\le a,b,c,d\le 10^8$$$).

## Output Format
For each test case, if it is possible to move from point $$$(a,b)$$$ to point $$$(c,d)$$$, output the minimum number of moves. Otherwise, output $$$-1$$$.

## Examples
```input
6
-1 0 -1 2
0 0 4 5
-2 -1 1 1
-3 2 -3 2
2 -1 -1 -1
1 1 0 2
```
```output
4
6
-1
0
3
3
```

## Note
In the first test case, one possible way using $$$4$$$ moves is $$$(-1,0)\to (0,1)\to (-1,1)\to (0,2)\to (-1,2)$$$. It can be proven that it is impossible to move from point $$$(-1,0)$$$ to point $$$(-1,2)$$$ in less than $$$4$$$ moves.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 1024.0 MB

# Problem
You are given an array $$$a$$$ of length $$$n$$$. The score of $$$a$$$ is the MEX$$$^{\dagger}$$$ of $$$[a_1+a_2,a_2+a_3,\ldots,a_{n-1}+a_n]$$$. Find the minimum score of $$$a$$$ if you are allowed to rearrange elements of $$$a$$$ in any order. Note that you are not required to construct the array $$$a$$$ that achieves the minimum score.

$$$^{\dagger}$$$ The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

- The MEX of $$$[2,2,1]$$$ is $$$0$$$, because $$$0$$$ does not belong to the array.
- The MEX of $$$[3,1,0,1]$$$ is $$$2$$$, because $$$0$$$ and $$$1$$$ belong to the array, but $$$2$$$ does not.
- The MEX of $$$[0,3,1,2]$$$ is $$$4$$$ because $$$0$$$, $$$1$$$, $$$2$$$, and $$$3$$$ belong to the array, but $$$4$$$ does not.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2\le n\le 2\cdot10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 2\cdot 10^5$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

## Output Format
For each test case, output the minimum score of $$$a$$$ after rearranging the elements of $$$a$$$ in any order.

## Examples
```input
3
2
0 0
3
0 0 1
8
1 0 0 0 2 0 3 0
```
```output
1
0
1
```

## Note
In the first test case, it is optimal to rearrange $$$a$$$ as $$$[0,0]$$$, the score of this array is the MEX of $$$[0+0]=[0]$$$, which is $$$1$$$.

In the second test case, it is optimal to rearrange $$$a$$$ as $$$[0,1,0]$$$, the score of this array is the MEX of $$$[0+1,1+0]=[1,1]$$$, which is $$$0$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 1024.0 MB

# Problem
For some positive integer $$$m$$$, YunQian considers an array $$$q$$$ of $$$2m$$$ (possibly negative) integers good, if and only if for every possible subsequence of $$$q$$$ that has length $$$m$$$, the product of the $$$m$$$ elements in the subsequence is equal to the sum of the $$$m$$$ elements that are not in the subsequence. Formally, let $$$U=\{1,2,\ldots,2m\}$$$. For all sets $$$S \subseteq U$$$ such that $$$|S|=m$$$, $$$\prod\limits_{i \in S} q_i = \sum\limits_{i \in U \setminus S} q_i$$$.

Define the distance between two arrays $$$a$$$ and $$$b$$$ both of length $$$k$$$ to be $$$\sum\limits_{i=1}^k|a_i-b_i|$$$.

You are given a positive integer $$$n$$$ and an array $$$p$$$ of $$$2n$$$ integers.

Find the minimum distance between $$$p$$$ and $$$q$$$ over all good arrays $$$q$$$ of length $$$2n$$$. It can be shown for all positive integers $$$n$$$, at least one good array exists. Note that you are not required to construct the array $$$q$$$ that achieves this minimum distance.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 2\cdot10^5$$$).

The second line of each test case contains $$$2n$$$ integers $$$p_1, p_2, \ldots, p_{2n}$$$ ($$$|p_i| \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

## Output Format
For each test case, output the minimum distance between $$$p$$$ and a good $$$q$$$.

## Examples
```input
4
1
6 9
2
1 2 2 1
2
-2 -2 2 2
4
-3 -2 -1 0 1 2 3 4
```
```output
3
2
5
13
```

## Note
In the first test case, it is optimal to let $$$q=[6,6]$$$.

In the second test case, it is optimal to let $$$q=[2,2,2,2]$$$.

Now solve the problem and return the code.