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
Ori and Sein have overcome many difficult challenges. They finally lit the Shrouded Lantern and found Gumon Seal, the key to the Forlorn Ruins. When they tried to open the door to the ruins... nothing happened.

Ori was very surprised, but Sein gave the explanation quickly: clever Gumon decided to make an additional defence for the door.

There are $$$n$$$ lamps with Spirit Tree's light. Sein knows the time of turning on and off for the $$$i$$$-th lamp — $$$l_i$$$ and $$$r_i$$$ respectively. To open the door you have to choose $$$k$$$ lamps in such a way that there will be a moment of time when they all will be turned on.

While Sein decides which of the $$$k$$$ lamps to pick, Ori is interested: how many ways there are to pick such $$$k$$$ lamps that the door will open? It may happen that Sein may be wrong and there are no such $$$k$$$ lamps. The answer might be large, so print it modulo $$$998\,244\,353$$$.

## Input Format
First line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$1 \le k \le n$$$) — total number of lamps and the number of lamps that must be turned on simultaneously.

Next $$$n$$$ lines contain two integers $$$l_i$$$ ans $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^9$$$) — period of time when $$$i$$$-th lamp is turned on.

## Output Format
Print one integer — the answer to the task modulo $$$998\,244\,353$$$.

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

## Note
In first test case there are nine sets of $$$k$$$ lamps: $$$(1, 2, 3)$$$, $$$(1, 2, 4)$$$, $$$(1, 2, 5)$$$, $$$(1, 2, 6)$$$, $$$(1, 3, 6)$$$, $$$(1, 4, 6)$$$, $$$(2, 3, 6)$$$, $$$(2, 4, 6)$$$, $$$(2, 6, 7)$$$.

In second test case $$$k=1$$$, so the answer is 3.

In third test case there are no such pairs of lamps.

In forth test case all lamps are turned on in a time $$$3$$$, so the answer is 1.

In fifth test case there are seven sets of $$$k$$$ lamps: $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(3, 4)$$$, $$$(3, 5)$$$, $$$(4, 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Lately, Mr. Chanek frequently plays the game Arena of Greed. As the name implies, the game's goal is to find the greediest of them all, who will then be crowned king of Compfestnesia.

The game is played by two people taking turns, where Mr. Chanek takes the first turn. Initially, there is a treasure chest containing $$$N$$$ gold coins. The game ends if there are no more gold coins in the chest. In each turn, the players can make one of the following moves:

- Take one gold coin from the chest.
- Take half of the gold coins on the chest. This move is only available if the number of coins in the chest is even.

Both players will try to maximize the number of coins they have. Mr. Chanek asks your help to find the maximum number of coins he can get at the end of the game if both he and the opponent plays optimally.

## Input Format
The first line contains a single integer $$$T$$$ $$$(1 \le T \le 10^5)$$$ denotes the number of test cases.

The next $$$T$$$ lines each contain a single integer $$$N$$$ $$$(1 \le N \le 10^{18})$$$.

## Output Format
$$$T$$$ lines, each line is the answer requested by Mr. Chanek.

## Examples
```input
2
5
6
```
```output
2
4
```

## Note
For the first case, the game is as follows:

1. Mr. Chanek takes one coin.
2. The opponent takes two coins.
3. Mr. Chanek takes one coin.
4. The opponent takes one coin.

For the second case, the game is as follows:

1. Mr. Chanek takes three coins.
2. The opponent takes one coin.
3. Mr. Chanek takes one coin.
4. The opponent takes one coin.

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
Mr. Chanek just won the national chess tournament and got a huge chessboard of size $$$N \times M$$$. Bored with playing conventional chess, Mr. Chanek now defines a function $$$F(X, Y)$$$, which denotes the minimum number of moves to move a knight from square $$$(1, 1)$$$ to square $$$(X, Y)$$$. It turns out finding $$$F(X, Y)$$$ is too simple, so Mr. Chanek defines:

$$$G(X, Y) = \sum_{i=X}^{N} \sum_{j=Y}^{M} F(i, j)$$$

Given X and Y, you are tasked to find $$$G(X, Y)$$$.

A knight can move from square $$$(a, b)$$$ to square $$$(a', b')$$$ if and only if $$$|a - a'| > 0$$$, $$$|b - b'| > 0$$$, and $$$|a - a'| + |b - b'| = 3$$$. Of course, the knight cannot leave the chessboard.

## Input Format
The first line contains an integer $$$T$$$ $$$(1 \le T \le 100)$$$, the number of test cases.

Each test case contains a line with four integers $$$X$$$ $$$Y$$$ $$$N$$$ $$$M$$$ $$$(3 \leq X \leq N \leq 10^9, 3 \leq Y \leq M \leq 10^9)$$$.

## Output Format
For each test case, print a line with the value of $$$G(X, Y)$$$ modulo $$$10^9 + 7$$$.

## Examples
```input
2
3 4 5 6
5 5 8 8
```
```output
27
70
```

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
Mr. Chanek The Ninja is one day tasked with a mission to handle mad snakes that are attacking a site. Now, Mr. Chanek already arrived at the hills where the destination is right below these hills. The mission area can be divided into a grid of size $$$1000 \times 1000$$$ squares. There are $$$N$$$ mad snakes on the site, the i'th mad snake is located on square $$$(X_i, Y_i)$$$ and has a danger level $$$B_i$$$.

Mr. Chanek is going to use the Shadow Clone Jutsu and Rasengan that he learned from Lord Seventh to complete this mission. His attack strategy is as follows:

1. Mr. Chanek is going to make $$$M$$$ clones.
2. Each clone will choose a mad snake as the attack target. Each clone must pick a different mad snake to attack.
3. All clones jump off the hills and attack their respective chosen target at once with Rasengan of radius $$$R$$$. If the mad snake at square $$$(X, Y)$$$ is attacked with a direct Rasengan, it and all mad snakes at squares $$$(X', Y')$$$ where $$$max(|X' - X|, |Y' - Y|) \le R$$$ will die.
4. The real Mr. Chanek will calculate the score of this attack. The score is defined as the square of the sum of the danger levels of all the killed snakes.

Now Mr. Chanek is curious, what is the sum of scores for every possible attack strategy? Because this number can be huge, Mr. Chanek only needs the output modulo $$$10^9 + 7$$$.

## Input Format
The first line contains three integers $$$N$$$ $$$M$$$ $$$R$$$ $$$(1 \le M \le N \le 2 \cdot 10^3, 0 \le R < 10^3)$$$, the number of mad snakes, the number of clones, and the radius of the Rasengan.

The next $$$N$$$ lines each contains three integers, $$$X_i$$$, $$$Y_i$$$, dan $$$B_i$$$ $$$(1 \le X_i, Y_i \le 10^3, 1 \le B_i \le 10^6)$$$. It is guaranteed that no two mad snakes occupy the same square.

## Output Format
A line with an integer that denotes the sum of scores for every possible attack strategy.

## Examples
```input
4 2 1
1 1 10
2 2 20
2 3 30
5 2 40
```
```output
33800
```

## Note
Here is the illustration of all six possible attack strategies. The circles denote the chosen mad snakes, and the blue squares denote the region of the Rasengan:

So, the total score of all attacks is: $$$3.600 + 3.600 + 4.900 + 3.600 + 10.000 + 8.100 = 33.800$$$.

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
Mr. Chanek is currently participating in a science fair that is popular in town. He finds an exciting puzzle in the fair and wants to solve it.

There are $$$N$$$ atoms numbered from $$$1$$$ to $$$N$$$. These atoms are especially quirky. Initially, each atom is in normal state. Each atom can be in an excited. Exciting atom $$$i$$$ requires $$$D_i$$$ energy. When atom $$$i$$$ is excited, it will give $$$A_i$$$ energy. You can excite any number of atoms (including zero).

These atoms also form a peculiar one-way bond. For each $$$i$$$, $$$(1 \le i < N)$$$, if atom $$$i$$$ is excited, atom $$$E_i$$$ will also be excited at no cost. Initially, $$$E_i$$$ = $$$i+1$$$. Note that atom $$$N$$$ cannot form a bond to any atom.

Mr. Chanek must change exactly $$$K$$$ bonds. Exactly $$$K$$$ times, Mr. Chanek chooses an atom $$$i$$$, $$$(1 \le i < N)$$$ and changes $$$E_i$$$ to a different value other than $$$i$$$ and the current $$$E_i$$$. Note that an atom's bond can remain unchanged or changed more than once. Help Mr. Chanek determine the maximum energy that he can achieve!

note: You must first change exactly $$$K$$$ bonds before you can start exciting atoms.

## Input Format
The first line contains two integers $$$N$$$ $$$K$$$ $$$(4 \le N \le 10^5, 0 \le K < N)$$$, the number of atoms, and the number of bonds that must be changed.

The second line contains $$$N$$$ integers $$$A_i$$$ $$$(1 \le A_i \le 10^6)$$$, which denotes the energy given by atom $$$i$$$ when on excited state.

The third line contains $$$N$$$ integers $$$D_i$$$ $$$(1 \le D_i \le 10^6)$$$, which denotes the energy needed to excite atom $$$i$$$.

## Output Format
A line with an integer that denotes the maximum number of energy that Mr. Chanek can get.

## Examples
```input
6 1
5 6 7 8 10 2
3 5 6 7 1 10
```
```output
35
```

## Note
An optimal solution to change $$$E_5$$$ to 1 and then excite atom 5 with energy 1. It will cause atoms 1, 2, 3, 4, 5 be excited. The total energy gained by Mr. Chanek is (5 + 6 + 7 + 8 + 10) - 1 = 35.

Another possible way is to change $$$E_3$$$ to 1 and then exciting atom 3 (which will excite atom 1, 2, 3) and exciting atom 4 (which will excite atom 4, 5, 6). The total energy gained by Mr. Chanek is (5 + 6 + 7 + 8 + 10 + 2) - (6 + 7) = 25 which is not optimal.

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're given an array $$$b$$$ of length $$$n$$$. Let's define another array $$$a$$$, also of length $$$n$$$, for which $$$a_i = 2^{b_i}$$$ ($$$1 \leq i \leq n$$$).

Valerii says that every two non-intersecting subarrays of $$$a$$$ have different sums of elements. You want to determine if he is wrong. More formally, you need to determine if there exist four integers $$$l_1,r_1,l_2,r_2$$$ that satisfy the following conditions:

If such four integers exist, you will prove Valerii wrong. Do they exist?

An array $$$c$$$ is a subarray of an array $$$d$$$ if $$$c$$$ can be obtained from $$$d$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

## 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 every test case contains a single integer $$$n$$$ ($$$2 \le n \le 1000$$$).

The second line of every test case contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ ($$$0 \le b_i \le 10^9$$$).

## Output Format
For every test case, if there exist two non-intersecting subarrays in $$$a$$$ that have the same sum, output YES on a separate line. Otherwise, output NO on a separate line.

Also, note that each letter can be in any case.

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

## Note
In the first case, $$$a = [16,8,1,2,4,1]$$$. Choosing $$$l_1 = 1$$$, $$$r_1 = 1$$$, $$$l_2 = 2$$$ and $$$r_2 = 6$$$ works because $$$16 = (8+1+2+4+1)$$$.

In the second case, you can verify that there is no way to select to such subarrays.

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
Artem is building a new robot. He has a matrix $$$a$$$ consisting of $$$n$$$ rows and $$$m$$$ columns. The cell located on the $$$i$$$-th row from the top and the $$$j$$$-th column from the left has a value $$$a_{i,j}$$$ written in it.

If two adjacent cells contain the same value, the robot will break. A matrix is called good if no two adjacent cells contain the same value, where two cells are called adjacent if they share a side.

Artem wants to increment the values in some cells by one to make $$$a$$$ good.

More formally, find a good matrix $$$b$$$ that satisfies the following condition —

- For all valid ($$$i,j$$$), either $$$b_{i,j} = a_{i,j}$$$ or $$$b_{i,j} = a_{i,j}+1$$$.

For the constraints of this problem, it can be shown that such a matrix $$$b$$$ always exists. If there are several such tables, you can output any of them. Please note that you do not have to minimize the number of increments.

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

The first line of each test case contains two integers $$$n, m$$$ ($$$1 \le n \le 100$$$, $$$1 \le m \le 100$$$)  — the number of rows and columns, respectively.

The following $$$n$$$ lines each contain $$$m$$$ integers. The $$$j$$$-th integer in the $$$i$$$-th line is $$$a_{i,j}$$$ ($$$1 \leq a_{i,j} \leq 10^9$$$).

## Output Format
For each case, output $$$n$$$ lines each containing $$$m$$$ integers. The $$$j$$$-th integer in the $$$i$$$-th line is $$$b_{i,j}$$$.

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

## Note
In all the cases, you can verify that no two adjacent cells have the same value and that $$$b$$$ is the same as $$$a$$$ with some values incremented by one.

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
Ksenia has an array $$$a$$$ consisting of $$$n$$$ positive integers $$$a_1, a_2, \ldots, a_n$$$.

In one operation she can do the following:

- choose three distinct indices $$$i$$$, $$$j$$$, $$$k$$$, and then
- change all of $$$a_i, a_j, a_k$$$ to $$$a_i \oplus a_j \oplus a_k$$$ simultaneously, where $$$\oplus$$$ denotes the bitwise XOR operation.

She wants to make all $$$a_i$$$ equal in at most $$$n$$$ operations, or to determine that it is impossible to do so. She wouldn't ask for your help, but please, help her!

## Input Format
The first line contains one integer $$$n$$$ ($$$3 \leq n \leq 10^5$$$) — the length of $$$a$$$.

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

## Output Format
Print YES or NO in the first line depending on whether it is possible to make all elements equal in at most $$$n$$$ operations.

If it is possible, print an integer $$$m$$$ ($$$0 \leq m \leq n$$$), which denotes the number of operations you do.

In each of the next $$$m$$$ lines, print three distinct integers $$$i, j, k$$$, representing one operation.

If there are many such operation sequences possible, print any. Note that you do not have to minimize the number of operations.

## Examples
```input
5
4 2 1 7 2
```
```output
YES
1
1 3 4
```
-----
```input
4
10 4 49 22
```
```output
NO
```

## Note
In the first example, the array becomes $$$[4 \oplus 1 \oplus 7, 2, 4 \oplus 1 \oplus 7, 4 \oplus 1 \oplus 7, 2] = [2, 2, 2, 2, 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Yurii is sure he can do everything. Can he solve this task, though?

He has an array $$$a$$$ consisting of $$$n$$$ positive integers. Let's call a subarray $$$a[l...r]$$$ good if the following conditions are simultaneously satisfied:

- $$$l+1 \leq r-1$$$, i. e. the subarray has length at least $$$3$$$;
- $$$(a_l \oplus a_r) = (a_{l+1}+a_{l+2}+\ldots+a_{r-2}+a_{r-1})$$$, where $$$\oplus$$$ denotes the bitwise XOR operation.

In other words, a subarray is good if the bitwise XOR of the two border elements is equal to the sum of the rest of the elements.

Yurii wants to calculate the total number of good subarrays. What is it equal to?

An array $$$c$$$ is a subarray of an array $$$d$$$ if $$$c$$$ can be obtained from $$$d$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

## Input Format
The first line contains a single integer $$$n$$$ ($$$3 \leq n \leq 2\cdot 10^5$$$) — the length of $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \lt 2^{30}$$$) — elements of $$$a$$$.

## Output Format
Output a single integer — the number of good subarrays.

## Examples
```input
8
3 1 2 3 1 2 3 15
```
```output
6
```
-----
```input
10
997230370 58052053 240970544 715275815 250707702 156801523 44100666 64791577 43523002 480196854
```
```output
2
```

## Note
There are $$$6$$$ good subarrays in the example:

- $$$[3,1,2]$$$ (twice) because $$$(3 \oplus 2) = 1$$$;
- $$$[1,2,3]$$$ (twice) because $$$(1 \oplus 3) = 2$$$;
- $$$[2,3,1]$$$ because $$$(2 \oplus 1) = 3$$$;
- $$$[3,1,2,3,1,2,3,15]$$$ because $$$(3 \oplus 15) = (1+2+3+1+2+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: 7.5 seconds
Memory limit: 256.0 MB

# Problem
You are given an integer $$$k$$$ and $$$n$$$ distinct points with integer coordinates on the Euclidean plane, the $$$i$$$-th point has coordinates $$$(x_i, y_i)$$$.

Consider a list of all the $$$\frac{n(n - 1)}{2}$$$ pairs of points $$$((x_i, y_i), (x_j, y_j))$$$ ($$$1 \le i < j \le n$$$). For every such pair, write out the distance from the line through these two points to the origin $$$(0, 0)$$$.

Your goal is to calculate the $$$k$$$-th smallest number among these distances.

## Input Format
The first line contains two integers $$$n$$$, $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le \frac{n(n - 1)}{2}$$$).

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^4 \le x_i, y_i \le 10^4$$$)  — the coordinates of the $$$i$$$-th point. It is guaranteed that all given points are pairwise distinct.

## Output Format
You should output one number — the $$$k$$$-th smallest distance from the origin. Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

## Examples
```input
4 3
2 1
-2 -1
0 -1
-2 4
```
```output
0.707106780737
```

## Note
There are $$$6$$$ pairs of points:

- Line $$$1-2$$$ : distance $$$0$$$ from the origin
- Line $$$1-3$$$ : distance $$$\frac{\sqrt{2}}{2} \approx 0.707106781$$$ from the origin
- Line $$$1-4$$$ : distance $$$2$$$ from the origin
- Line $$$2-3$$$ : distance $$$1$$$ from the origin
- Line $$$2-4$$$ : distance $$$2$$$ from the origin
- Line $$$3-4$$$ : distance $$$\frac{2}{\sqrt{29}} \approx 0.371390676$$$ from the origin

Now solve the problem and return the code.