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

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Lord Omkar has permitted you to enter the Holy Church of Omkar! To test your worthiness, Omkar gives you a password which you must interpret!

A password is an array $$$a$$$ of $$$n$$$ positive integers. You apply the following operation to the array: pick any two adjacent numbers that are not equal to each other and replace them with their sum. Formally, choose an index $$$i$$$ such that $$$1 \leq i < n$$$ and $$$a_{i} \neq a_{i+1}$$$, delete both $$$a_i$$$ and $$$a_{i+1}$$$ from the array and put $$$a_{i}+a_{i+1}$$$ in their place.

For example, for array $$$[7, 4, 3, 7]$$$ you can choose $$$i = 2$$$ and the array will become $$$[7, 4+3, 7] = [7, 7, 7]$$$. Note that in this array you can't apply this operation anymore.

Notice that one operation will decrease the size of the password by $$$1$$$. What is the shortest possible length of the password after some number (possibly $$$0$$$) of operations?

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). Description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of the password.

The second line of each test case contains $$$n$$$ integers $$$a_{1},a_{2},\dots,a_{n}$$$ ($$$1 \leq a_{i} \leq 10^9$$$) — the initial contents of your password.

The sum of $$$n$$$ over all test cases will not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each password, print one integer: the shortest possible length of the password after some number of operations.

## Examples
```input
2
4
2 1 3 1
2
420 420
```
```output
1
2
```

## Note
In the first test case, you can do the following to achieve a length of $$$1$$$:

Pick $$$i=2$$$ to get $$$[2, 4, 1]$$$

Pick $$$i=1$$$ to get $$$[6, 1]$$$

Pick $$$i=1$$$ to get $$$[7]$$$

In the second test case, you can't perform any operations because there is no valid $$$i$$$ that satisfies the requirements mentioned above.

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

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Being stuck at home, Ray became extremely bored. To pass time, he asks Lord Omkar to use his time bending power: Infinity Clock! However, Lord Omkar will only listen to mortals who can solve the following problem:

You are given an array $$$a$$$ of $$$n$$$ integers. You are also given an integer $$$k$$$. Lord Omkar wants you to do $$$k$$$ operations with this array.

Define one operation as the following:

1. Set $$$d$$$ to be the maximum value of your array.
2. For every $$$i$$$ from $$$1$$$ to $$$n$$$, replace $$$a_{i}$$$ with $$$d-a_{i}$$$.

The goal is to predict the contents in the array after $$$k$$$ operations. Please help Ray determine what the final sequence will look like!

## Input Format
Each test contains multiple test cases. The first line contains the number of cases $$$t$$$ ($$$1 \le t \le 100$$$). 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, 1 \leq k \leq 10^{18}$$$) – the length of your array and the number of operations to perform.

The second line of each test case contains $$$n$$$ integers $$$a_{1},a_{2},...,a_{n}$$$ $$$(-10^9 \leq a_{i} \leq 10^9)$$$ – the initial contents of your array.

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

## Output Format
For each case, print the final version of array $$$a$$$ after $$$k$$$ operations described above.

## Examples
```input
3
2 1
-199 192
5 19
5 -1 4 2 0
1 2
69
```
```output
391 0
0 6 1 3 5
0
```

## Note
In the first test case the array changes as follows:

- Initially, the array is $$$[-199, 192]$$$. $$$d = 192$$$.
- After the operation, the array becomes $$$[d-(-199), d-192] = [391, 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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
zscoder has a deck of $$$n+m$$$ custom-made cards, which consists of $$$n$$$ cards labelled from $$$1$$$ to $$$n$$$ and $$$m$$$ jokers. Since zscoder is lonely, he wants to play a game with himself using those cards.

Initially, the deck is shuffled uniformly randomly and placed on the table. zscoder has a set $$$S$$$ which is initially empty.

Every second, zscoder draws the top card from the deck.

- If the card has a number $$$x$$$ written on it, zscoder removes the card and adds $$$x$$$ to the set $$$S$$$.
- If the card drawn is a joker, zscoder places all the cards back into the deck and reshuffles (uniformly randomly) the $$$n+m$$$ cards to form a new deck (hence the new deck now contains all cards from $$$1$$$ to $$$n$$$ and the $$$m$$$ jokers). Then, if $$$S$$$ currently contains all the elements from $$$1$$$ to $$$n$$$, the game ends. Shuffling the deck doesn't take time at all.

What is the expected number of seconds before the game ends? We can show that the answer can be written in the form $$$\frac{P}{Q}$$$ where $$$P, Q$$$ are relatively prime integers and $$$Q \neq 0 \bmod 998244353$$$. Output the value of $$$(P \cdot Q^{-1})$$$ modulo $$$998244353$$$.

## Input Format
The only line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^{6}$$$).

## Output Format
Output a single integer, the value of $$$(P \cdot Q^{-1})$$$ modulo $$$998244353$$$.

## Examples
```input
2 1
```
```output
5
```
-----
```input
3 2
```
```output
332748127
```
-----
```input
14 9
```
```output
969862773
```

## Note
For the first sample, it can be proven that the expected time before the game ends is $$$5$$$ seconds.

For the second sample, it can be proven that the expected time before the game ends is $$$\frac{28}{3}$$$ seconds.

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

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:
```python
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 512.0 MB

# Problem
Shrimpy Duc is a fat and greedy boy who is always hungry. After a while of searching for food to satisfy his never-ending hunger, Shrimpy Duc finds M&M candies lying unguarded on a $$$L \times L$$$ grid. There are $$$n$$$ M&M candies on the grid, the $$$i$$$-th M&M is currently located at $$$(x_i + 0.5, y_i + 0.5),$$$ and has color $$$c_i$$$ out of a total of $$$k$$$ colors (the size of M&Ms are insignificant).

Shrimpy Duc wants to steal a rectangle of M&Ms, specifically, he wants to select a rectangle with integer coordinates within the grid and steal all candies within the rectangle. Shrimpy Duc doesn't need to steal every single candy, however, he would like to steal at least one candy for each color.

In other words, he wants to select a rectangle whose sides are parallel to the coordinate axes and whose left-bottom vertex $$$(X_1, Y_1)$$$ and right-top vertex $$$(X_2, Y_2)$$$ are points with integer coordinates satisfying $$$0 \le X_1 < X_2 \le L$$$ and $$$0 \le Y_1 < Y_2 \le L$$$, so that for every color $$$1 \le c \le k$$$ there is at least one M&M with color $$$c$$$ that lies within that rectangle.

How many such rectangles are there? This number may be large, so you only need to find it modulo $$$10^9 + 7$$$.

## Input Format
The first line contains three positive integers $$$n, k, L$$$ $$$(1 \leq k \leq n \leq 2 \cdot 10^3, 1 \leq L \leq 10^9 )$$$ — the number of M&Ms, the number of colors and the length of the grid respectively.

The following $$$n$$$ points describe the M&Ms. Each line contains three integers $$$x_i, y_i, c_i$$$ $$$(0 \leq x_i, y_i < L, 1 \le c_i \le k)$$$ — the coordinates and color of the $$$i$$$-th M&M respectively.

Different M&Ms have different coordinates ($$$x_i \ne x_j$$$ or $$$y_i \ne y_j$$$ for every $$$i \ne j$$$), and for every $$$1 \le c \le k$$$ there is at least one M&M with color $$$c$$$.

## Output Format
Output a single integer — the number of rectangles satisfying Shrimpy Duc's conditions, modulo $$$10^9 + 7$$$.

## Examples
```input
4 2 4
3 2 2
3 1 1
1 1 1
1 2 1
```
```output
20
```
-----
```input
5 3 10
6 5 3
5 3 1
7 9 1
2 3 2
5 0 2
```
```output
300
```
-----
```input
10 4 10
5 4 4
0 0 3
6 0 1
3 9 2
8 7 1
8 1 3
2 1 3
6 3 2
3 5 3
4 3 4
```
```output
226
```

## Note
Grid for the first sample:

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

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an integer $$$k$$$ and a tree $$$T$$$ with $$$n$$$ nodes ($$$n$$$ is even).

Let $$$dist(u, v)$$$ be the number of edges on the shortest path from node $$$u$$$ to node $$$v$$$ in $$$T$$$.

Let us define a undirected weighted complete graph $$$G = (V, E)$$$ as following:

- $$$V = \{x \mid 1 \le x \le n \}$$$ i.e. the set of integers from $$$1$$$ to $$$n$$$
- $$$E = \{(u, v, w) \mid 1 \le u, v \le n, u \neq v, w = dist(u, v) \}$$$ i.e. there is an edge between every pair of distinct nodes, the weight being the distance between their respective nodes in $$$T$$$

Your task is simple, find a perfect matching in $$$G$$$ with total edge weight $$$k$$$ $$$(1 \le k \le n^2)$$$.

## Input Format
The first line of input contains two integers $$$n$$$, $$$k$$$ ($$$2 \le n \le 100\,000$$$, $$$n$$$ is even, $$$1 \le k \le n^2$$$): number of nodes and the total edge weight of the perfect matching you need to find.

The $$$i$$$-th of the following $$$n - 1$$$ lines contains two integers $$$v_i$$$, $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) denoting an edge between $$$v_i$$$ and $$$u_i$$$ in $$$T$$$. It is guaranteed that the given graph is a tree.

## Output Format
If there are no matchings that satisfy the above condition, output "NO" (without quotes) on a single line.

Otherwise, you should output "YES" (without quotes) on the first line of output.

You should then output $$$\frac{n}{2}$$$ lines, the $$$i$$$-th line containing $$$p_i, q_i$$$ ($$$1 \le p_i, q_i \le n$$$): the $$$i$$$-th pair of the matching.

## Examples
```input
4 2
1 2
2 3
3 4
```
```output
YES
2 1
3 4
```
-----
```input
4 4
1 2
2 3
3 4
```
```output
YES
3 1
2 4
```

## Note
A tree is a connected acyclic undirected graph.

A matching is set of pairwise non-adjacent edges, none of which are loops; that is, no two edges share a common vertex.

A perfect matching is a matching which matches all vertices of the graph; that is, every vertex of the graph is incident to exactly one edge of the matching.

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

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 512.0 MB

# Problem
Given a set of integers (it can contain equal elements).

You have to split it into two subsets $$$A$$$ and $$$B$$$ (both of them can contain equal elements or be empty). You have to maximize the value of $$$mex(A)+mex(B)$$$.

Here $$$mex$$$ of a set denotes the smallest non-negative integer that doesn't exist in the set. For example:

- $$$mex(\{1,4,0,2,2,1\})=3$$$
- $$$mex(\{3,3,2,1,3,0,0\})=4$$$
- $$$mex(\varnothing)=0$$$ ($$$mex$$$ for empty set)

The set is splitted into two subsets $$$A$$$ and $$$B$$$ if for any integer number $$$x$$$ the number of occurrences of $$$x$$$ into this set is equal to the sum of the number of occurrences of $$$x$$$ into $$$A$$$ and the number of occurrences of $$$x$$$ into $$$B$$$.

## Input Format
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1\leq t\leq 100$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1\leq n\leq 100$$$) — the size of the set.

The second line of each testcase contains $$$n$$$ integers $$$a_1,a_2,\dots a_n$$$ ($$$0\leq a_i\leq 100$$$) — the numbers in the set.

## Output Format
For each test case, print the maximum value of $$$mex(A)+mex(B)$$$.

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

## Note
In the first test case, $$$A=\left\{0,1,2\right\},B=\left\{0,1,5\right\}$$$ is a possible choice.

In the second test case, $$$A=\left\{0,1,2\right\},B=\varnothing$$$ is a possible choice.

In the third test case, $$$A=\left\{0,1,2\right\},B=\left\{0\right\}$$$ is a possible choice.

In the fourth test case, $$$A=\left\{1,3,5\right\},B=\left\{2,4,6\right\}$$$ is a possible choice.

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

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an array of integers $$$a_1,a_2,\ldots,a_n$$$. Find the maximum possible value of $$$a_ia_ja_ka_la_t$$$ among all five indices $$$(i, j, k, l, t)$$$ ($$$i<j<k<l<t$$$).

## Input Format
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1\le t\le 2 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$5\le n\le 10^5$$$) — the size of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$-3\times 10^3\le a_i\le 3\times 10^3$$$) — given array.

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

## Output Format
For each test case, print one integer — the answer to the problem.

## Examples
```input
4
5
-1 -2 -3 -4 -5
6
-1 -2 -3 1 2 -1
6
-1 0 0 0 -1 -1
6
-9 -7 -5 -3 -2 1
```
```output
-120
12
0
945
```

## Note
In the first test case, choosing $$$a_1,a_2,a_3,a_4,a_5$$$ is a best choice: $$$(-1)\cdot (-2) \cdot (-3)\cdot (-4)\cdot (-5)=-120$$$.

In the second test case, choosing $$$a_1,a_2,a_3,a_5,a_6$$$ is a best choice: $$$(-1)\cdot (-2) \cdot (-3)\cdot 2\cdot (-1)=12$$$.

In the third test case, choosing $$$a_1,a_2,a_3,a_4,a_5$$$ is a best choice: $$$(-1)\cdot 0\cdot 0\cdot 0\cdot (-1)=0$$$.

In the fourth test case, choosing $$$a_1,a_2,a_3,a_4,a_6$$$ is a best choice: $$$(-9)\cdot (-7) \cdot (-5)\cdot (-3)\cdot 1=945$$$.

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

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You are given a sequence of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$.

You have to construct two sequences of integers $$$b$$$ and $$$c$$$ with length $$$n$$$ that satisfy:

- for every $$$i$$$ ($$$1\leq i\leq n$$$) $$$b_i+c_i=a_i$$$
- $$$b$$$ is non-decreasing, which means that for every $$$1<i\leq n$$$, $$$b_i\geq b_{i-1}$$$ must hold
- $$$c$$$ is non-increasing, which means that for every $$$1<i\leq n$$$, $$$c_i\leq c_{i-1}$$$ must hold

You have to minimize $$$\max(b_i,c_i)$$$. In other words, you have to minimize the maximum number in sequences $$$b$$$ and $$$c$$$.

Also there will be $$$q$$$ changes, the $$$i$$$-th change is described by three integers $$$l,r,x$$$. You should add $$$x$$$ to $$$a_l,a_{l+1}, \ldots, a_r$$$.

You have to find the minimum possible value of $$$\max(b_i,c_i)$$$ for the initial sequence and for sequence after each change.

## Input Format
The first line contains an integer $$$n$$$ ($$$1\leq n\leq 10^5$$$).

The secound line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq i\leq n$$$, $$$-10^9\leq a_i\leq 10^9$$$).

The third line contains an integer $$$q$$$ ($$$1\leq q\leq 10^5$$$).

Each of the next $$$q$$$ lines contains three integers $$$l,r,x$$$ ($$$1\leq l\leq r\leq n,-10^9\leq x\leq 10^9$$$), desribing the next change.

## Output Format
Print $$$q+1$$$ lines.

On the $$$i$$$-th ($$$1 \leq i \leq q+1$$$) line, print the answer to the problem for the sequence after $$$i-1$$$ changes.

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

## Note
In the first test:

- The initial sequence $$$a = (2, -1, 7, 3)$$$. Two sequences $$$b=(-3,-3,5,5),c=(5,2,2,-2)$$$ is a possible choice.
- After the first change $$$a = (2, -4, 4, 0)$$$. Two sequences $$$b=(-3,-3,5,5),c=(5,-1,-1,-5)$$$ is a possible choice.
- After the second change $$$a = (2, -4, 6, 2)$$$. Two sequences $$$b=(-4,-4,6,6),c=(6,0,0,-4)$$$ is a possible choice.

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

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
There are $$$n$$$ districts in the town, the $$$i$$$-th district belongs to the $$$a_i$$$-th bandit gang. Initially, no districts are connected to each other.

You are the mayor of the city and want to build $$$n-1$$$ two-way roads to connect all districts (two districts can be connected directly or through other connected districts).

If two districts belonging to the same gang are connected directly with a road, this gang will revolt.

You don't want this so your task is to build $$$n-1$$$ two-way roads in such a way that all districts are reachable from each other (possibly, using intermediate districts) and each pair of directly connected districts belong to different gangs, or determine that it is impossible to build $$$n-1$$$ roads to satisfy all the conditions.

You have to answer $$$t$$$ independent test cases.

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

The first line of the test case contains one integer $$$n$$$ ($$$2 \le n \le 5000$$$) — the number of districts. The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the gang the $$$i$$$-th district belongs to.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$5000$$$ ($$$\sum n \le 5000$$$).

## Output Format
For each test case, print:

- NO on the only line if it is impossible to connect all districts satisfying the conditions from the problem statement.
- YES on the first line and $$$n-1$$$ roads on the next $$$n-1$$$ lines. Each road should be presented as a pair of integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n; x_i \ne y_i$$$), where $$$x_i$$$ and $$$y_i$$$ are two districts the $$$i$$$-th road connects.

For each road $$$i$$$, the condition $$$a[x_i] \ne a[y_i]$$$ should be satisfied. Also, all districts should be reachable from each other (possibly, using intermediate districts).

## Examples
```input
4
5
1 2 2 1 3
3
1 1 1
4
1 1000 101 1000
4
1 2 3 4
```
```output
YES
1 3
3 5
5 4
1 2
NO
YES
1 2
2 3
3 4
YES
1 2
1 3
1 4
```

Now solve the problem and return the code.