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
The Zoo in the Grid Kingdom is represented by an infinite grid. The Zoo has n observation binoculars located at the OX axis. For each i between 1 and n, inclusive, there exists a single binocular located at the point with coordinates (i, 0). There are m flamingos in the Zoo, located at points with positive coordinates. The flamingos are currently sleeping and you can assume that they don't move.

In order to get a good view over the flamingos, each of the binoculars can be independently rotated to face any angle (not necessarily integer). Then, the binocular can be used to observe all flamingos that is located at the straight line passing through the binocular at the angle it is set. In other words, you can assign each binocular a direction corresponding to any straight line passing through the binocular, and the binocular will be able to see all flamingos located on that line.

Today, some kids from the prestigious Codeforces kindergarten went on a Field Study to the Zoo. Their teacher would like to set each binocular an angle to maximize the number of flamingos that can be seen by the binocular. The teacher is very interested in the sum of these values over all binoculars. Please help him find this sum.

## Input Format
The first line contains two space-separated integers n and m (1 ≤ n ≤ 106, 1 ≤ m ≤ 250), denoting the number of binoculars and the number of flamingos, respectively.

Then m lines follow, the i-th line will contain two space-separated integers xi and yi (1 ≤ xi, yi ≤ 109), which means that the i-th flamingo is located at point (xi, yi).

All flamingos will be located at distinct points.

## Output Format
Print a single integer denoting the maximum total number of flamingos that can be seen by all the binoculars.

## Examples
```input
5 5
2 1
4 1
3 2
4 3
4 4
```
```output
11
```

## Note
This picture shows the answer to the example test case.

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: 4.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a directed graph G with n vertices and m arcs (multiple arcs and self-loops are allowed). You have to paint each vertex of the graph into one of the k (k ≤ n) colors in such way that for all arcs of the graph leading from a vertex u to vertex v, vertex v is painted with the next color of the color used to paint vertex u.

The colors are numbered cyclically 1 through k. This means that for each color i (i < k) its next color is color i + 1. In addition, the next color of color k is color 1. Note, that if k = 1, then the next color for color 1 is again color 1.

Your task is to find and print the largest possible value of k (k ≤ n) such that it's possible to color G as described above with k colors. Note that you don't necessarily use all the k colors (that is, for each color i there does not necessarily exist a vertex that is colored with color i).

## Input Format
The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 105), denoting the number of vertices and the number of arcs of the given digraph, respectively.

Then m lines follow, each line will contain two space-separated integers ai and bi (1 ≤ ai, bi ≤ n), which means that the i-th arc goes from vertex ai to vertex bi.

Multiple arcs and self-loops are allowed.

## Output Format
Print a single integer — the maximum possible number of the colors that can be used to paint the digraph (i.e. k, as described in the problem statement). Note that the desired value of k must satisfy the inequality 1 ≤ k ≤ n.

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

## Note
For the first example, with k = 2, this picture depicts the two colors (arrows denote the next color of that color).

With k = 2 a possible way to paint the graph is as follows.

It can be proven that no larger value for k exists for this test case.

For the second example, here's the picture of the k = 5 colors.

A possible coloring of the graph is:

For the third example, here's the picture of the k = 3 colors.

A possible coloring of the graph is:

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: 256.0 MB

# Problem
You are given an array $$$a$$$ of $$$n$$$ integers, where all elements $$$a_i$$$ lie in the range $$$[1, k]$$$. How many different arrays $$$b$$$ of $$$m$$$ integers, where all elements $$$b_i$$$ lie in the range $$$[1, k]$$$, contain $$$a$$$ as a subsequence? Two arrays are considered different if they differ in at least one position.

A sequence $$$x$$$ is a subsequence of a sequence $$$y$$$ if $$$x$$$ can be obtained from $$$y$$$ by the deletion of several (possibly, zero or all) elements.

Since the answer may be large, print it modulo $$$10^9 + 7$$$.

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

The first line of each test case contains three integers $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \le n \le 2\cdot 10^5$$$, $$$n \le m \le 10^9$$$, $$$1 \le k \le 10^9$$$) — the size of $$$a$$$, the size of $$$b$$$, and the maximum value allowed in the arrays, respectively.

The next line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots a_n$$$ ($$$1\le a_i \le k$$$) — the elements of the array $$$a$$$.

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 a single integer — the number of suitable arrays $$$b$$$, modulo $$$10^9+7$$$.

## Examples
```input
7
1 1000000 1
1
3 4 3
1 2 2
5 7 8
1 2 3 4 1
6 6 18
18 2 2 5 2 16
1 10 2
1
8 10 1234567
1 1 2 1 2 2 2 1
5 1000000000 1000000000
525785549 816356460 108064697 194447117 725595511
```
```output
1
9
1079
1
1023
906241579
232432822
```

## Note
For the first example, since $$$k=1$$$, there is only one array of size $$$m$$$ consisting of the integers $$$[1, k]$$$. This array ($$$[1, 1, \ldots, 1]$$$) contains the original array as a subsequence, so the answer is 1.

For the second example, the $$$9$$$ arrays are $$$[1, 1, 2, 2]$$$, $$$[1, 2, 1, 2]$$$, $$$[1, 2, 2, 1]$$$, $$$[1, 2, 2, 2]$$$, $$$[1, 2, 2, 3]$$$, $$$[1, 2, 3, 2]$$$, $$$[1, 3, 2, 2]$$$, $$$[2, 1, 2, 2]$$$, $$$[3, 1, 2, 2]$$$.

For the fourth example, since $$$m=n$$$, the only array of size $$$m$$$ that contains $$$a$$$ as a subsequence is $$$a$$$ itself.

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
Tenzing has $$$n$$$ balls arranged in a line. The color of the $$$i$$$-th ball from the left is $$$a_i$$$.

Tenzing can do the following operation any number of times:

- select $$$i$$$ and $$$j$$$ such that $$$1\leq i < j \leq |a|$$$ and $$$a_i=a_j$$$,
- remove $$$a_i,a_{i+1},\ldots,a_j$$$ from the array (and decrease the indices of all elements to the right of $$$a_j$$$ by $$$j-i+1$$$).

Tenzing wants to know the maximum number of balls he can remove.

## Input Format
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1\leq t\leq 10^3$$$) — the number of test cases. The description of test cases follows.

The first line contains a single integer $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$) — the number of balls.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_i \leq n$$$) — the color of the balls.

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

## Output Format
For each test case, output the maximum number of balls Tenzing can remove.

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

## Note
In the first example, Tenzing will choose $$$i=2$$$ and $$$j=3$$$ in the first operation so that $$$a=[1,3,3]$$$. Then Tenzing will choose $$$i=2$$$ and $$$j=3$$$ again in the second operation so that $$$a=[1]$$$. So Tenzing can remove $$$4$$$ balls in total.

In the second example, Tenzing will choose $$$i=1$$$ and $$$j=3$$$ in the first and only operation so that $$$a=[2]$$$. So Tenzing can remove $$$3$$$ balls in total.

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
Tenzing has an undirected tree of $$$n$$$ vertices.

Define the value of a tree with black and white vertices in the following way. The value of an edge is the absolute difference between the number of black nodes in the two components of the tree after deleting the edge. The value of the tree is the sum of values over all edges.

For all $$$k$$$ such that $$$0 \leq k \leq n$$$, Tenzing wants to know the maximum value of the tree when $$$k$$$ vertices are painted black and $$$n-k$$$ vertices are painted white.

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

The following $$$n-1$$$ lines of the input contains $$$2$$$ integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n, u_i \neq v_i$$$) — indicating an edge between vertices $$$u_i$$$ and $$$v_i$$$. It is guaranteed that the given edges form a tree.

## Output Format
Output $$$n+1$$$ numbers. The $$$i$$$-th number is the answer of $$$k=i-1$$$.

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

## Note
Consider the first example. When $$$k=2$$$, Tenzing can paint vertices $$$1$$$ and $$$2$$$ black then the value of edge $$$(1,2)$$$ is 0, and the values of other edges are all equal to $$$2$$$. So the value of that tree is $$$4$$$.

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: 1024.0 MB

# Problem
Tenzing has an array $$$a$$$ of length $$$n$$$ and an integer $$$v$$$.

Tenzing will perform the following operation $$$m$$$ times:

1. Choose an integer $$$i$$$ such that $$$1 \leq i \leq n$$$ uniformly at random.
2. For all $$$j$$$ such that $$$i \leq j \leq n$$$, set $$$a_j := a_j + v$$$.

Tenzing wants to know the expected value of $$$\prod_{i=1}^n a_i$$$ after performing the $$$m$$$ operations, modulo $$$10^9+7$$$.

Formally, let $$$M = 10^9+7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output the integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

## Input Format
The first line of input contains three integers $$$n$$$, $$$m$$$ and $$$v$$$ ($$$1\leq n\leq 5000$$$, $$$1\leq m,v\leq 10^9$$$).

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

## Output Format
Output the expected value of $$$\prod_{i=1}^n a_i$$$ modulo $$$10^9+7$$$.

## Examples
```input
2 2 5
2 2
```
```output
84
```
-----
```input
5 7 9
9 9 8 2 4
```
```output
975544726
```

## Note
There are three types of $$$a$$$ after performing all the $$$m$$$ operations :

1. $$$a_1=2,a_2=12$$$ with $$$\frac{1}{4}$$$ probability.

2. $$$a_1=a_2=12$$$ with $$$\frac{1}{4}$$$ probability.

3. $$$a_1=7,a_2=12$$$ with $$$\frac{1}{2}$$$ probability.

So the expected value of $$$a_1\cdot a_2$$$ is $$$\frac{1}{4}\cdot (24+144) + \frac{1}{2}\cdot 84=84$$$.

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
There are $$$n$$$ uniform random real variables between 0 and 1, inclusive, which are denoted as $$$x_1, x_2, \ldots, x_n$$$.

Tenzing has $$$m$$$ conditions. Each condition has the form of $$$x_i+x_j\le 1$$$ or $$$x_i+x_j\ge 1$$$.

Tenzing wants to know the probability that all the conditions are satisfied, modulo $$$998~244~353$$$.

Formally, let $$$M = 998~244~353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output the integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n\le 20$$$, $$$0\le m\le n^2+n$$$).

Then following $$$m$$$ lines of input contains three integers $$$t$$$, $$$i$$$ and $$$j$$$ ($$$t \in \{0,1\}$$$, $$$1\le i\le j\le n$$$).

- If $$$t=0$$$, the condition is $$$x_i+x_j\le 1$$$.
- If $$$t=1$$$, the condition is $$$x_i+x_j\ge 1$$$.

It is guaranteed that all conditions are pairwise distinct.

## Output Format
Output the probability that all the conditions are satisfied, modulo $$$M = 998~244~353$$$.

## Examples
```input
3 2
0 1 2
1 3 3
```
```output
748683265
```
-----
```input
3 3
0 1 2
0 1 3
0 2 3
```
```output
748683265
```
-----
```input
3 4
0 1 2
0 1 3
1 2 3
1 2 2
```
```output
935854081
```
-----
```input
4 4
0 1 2
0 3 4
1 1 3
1 2 4
```
```output
0
```
-----
```input
8 12
0 1 2
0 2 3
1 3 4
0 1 4
0 5 6
0 6 7
1 7 8
0 5 8
1 3 7
1 3 8
1 4 7
1 4 8
```
```output
997687297
```

## Note
In the first test case, the conditions are $$$x_1+x_2 \le 1$$$ and $$$x_3+x_3\ge 1$$$, and the probability that each condition is satisfied is $$$\frac 12$$$, so the probability that they are both satisfied is $$$\frac 12\cdot \frac 12=\frac 14$$$, modulo $$$998~244~353$$$ is equal to $$$748683265$$$.

In the second test case, the answer is $$$\frac 14$$$.

In the third test case, the answer is $$$\frac 1{16}$$$.

In the fourth test case, the sum of all variables must equal $$$2$$$, so the probability 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: 2.0 seconds
Memory limit: 1024.0 MB

# Problem
Tenzing has a beautiful necklace. The necklace consists of $$$n$$$ pearls numbered from $$$1$$$ to $$$n$$$ with a string connecting pearls $$$i$$$ and $$$(i \text{ mod } n)+1$$$ for all $$$1 \leq i \leq n$$$.

One day Tenzing wants to cut the necklace into several parts by cutting some strings. But for each connected part of the necklace, there should not be more than $$$k$$$ pearls. The time needed to cut each string may not be the same. Tenzing needs to spend $$$a_i$$$ minutes cutting the string between pearls $$$i$$$ and $$$(i \text{ mod } n)+1$$$.

Tenzing wants to know the minimum time in minutes to cut the necklace such that each connected part will not have more than $$$k$$$ pearls.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2\leq n\leq 5\cdot 10^5$$$, $$$1\leq k <n$$$).

The second line of each test case 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$$$ of all test cases does not exceed $$$5 \cdot 10^5$$$.

## Output Format
For each test case, output the minimum total time in minutes required.

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

## Note
In the first test case, the necklace will be cut into $$$3$$$ parts: $$$[1,2][3,4][5]$$$, so the total time is $$$3$$$.

In the second test case, the necklace will be cut into $$$3$$$ parts: $$$[5,1][2][3,4]$$$, Tenzing will cut the strings connecting $$$(1,2), (2,3)$$$ and $$$(4,5)$$$, so the total time is $$$a_1+a_2+a_4=7$$$.

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
There are $$$n$$$ nails driven into the wall, the $$$i$$$-th nail is driven $$$a_i$$$ meters above the ground, one end of the $$$b_i$$$ meters long rope is tied to it. All nails hang at different heights one above the other. One candy is tied to all ropes at once. Candy is tied to end of a rope that is not tied to a nail.

To take the candy, you need to lower it to the ground. To do this, Rudolph can cut some ropes, one at a time. Help Rudolph find the minimum number of ropes that must be cut to get the candy.

The figure shows an example of the first test:

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

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 50$$$) — the number of nails.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le 200$$$) — the height of the $$$i$$$-th nail and the length of the rope tied to it, all $$$a_i$$$ are different.

It is guaranteed that the data is not contradictory, it is possible to build a configuration described in the statement.

## Output Format
For each test case print one integer — the minimum number of ropes that need to be cut to make the candy fall to the ground.

## Examples
```input
4
3
4 3
3 1
1 2
4
9 2
5 2
7 7
3 4
5
11 7
5 10
12 9
3 2
1 5
3
5 6
4 5
7 7
```
```output
2
2
3
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: 256.0 MB

# Problem
Rudolph invented the game of tic-tac-toe for three players. It has classic rules, except for the third player who plays with pluses. Rudolf has a $$$3 \times 3$$$ field  — the result of the completed game. Each field cell contains either a cross, or a nought, or a plus sign, or nothing. The game is won by the player who makes a horizontal, vertical or diagonal row of $$$3$$$'s of their symbols.

Rudolph wants to find the result of the game. Either exactly one of the three players won or it ended in a draw. It is guaranteed that multiple players cannot win at the same time.

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

Each test case consists of three lines, each of which consists of three characters. The symbol can be one of four: "X" means a cross, "O" means a nought, "+" means a plus, "." means an empty cell.

## Output Format
For each test case, print the string "X" if the crosses won, "O" if the noughts won, "+" if the pluses won, "DRAW" if there was a draw.

## Examples
```input
5
+X+
OXO
OX.
O+.
+OX
X+O
.XO
OX.
+++
O.+
X.O
+..
.++
X.O
+..
```
```output
X
O
+
DRAW
DRAW
```

Now solve the problem and return the code.