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

# Problem
It is the hard version of the problem. The only difference is that in this version $$$a_i \le 10^9$$$.

You are given an array of $$$n$$$ integers $$$a_0, a_1, a_2, \ldots a_{n - 1}$$$. Bryap wants to find the longest beautiful subsequence in the array.

An array $$$b = [b_0, b_1, \ldots, b_{m-1}]$$$, where $$$0 \le b_0 < b_1 < \ldots < b_{m - 1} < n$$$, is a subsequence of length $$$m$$$ of the array $$$a$$$.

Subsequence $$$b = [b_0, b_1, \ldots, b_{m-1}]$$$ of length $$$m$$$ is called beautiful, if the following condition holds:

- For any $$$p$$$ ($$$0 \le p < m - 1$$$) holds: $$$a_{b_p} \oplus b_{p+1} < a_{b_{p+1}} \oplus b_p$$$.

Here $$$a \oplus b$$$ denotes the bitwise XOR of $$$a$$$ and $$$b$$$. For example, $$$2 \oplus 4 = 6$$$ and $$$3 \oplus 1=2$$$.

Bryap is a simple person so he only wants to know the length of the longest such subsequence. Help Bryap and find the answer to his question.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_0,a_1,...,a_{n-1}$$$ ($$$0 \leq a_i \leq 10^9$$$) — the elements of the array.

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

## Output Format
For each test case print a single integer — the length of the longest beautiful subsequence.

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

## Note
In the first test case, we can pick the whole array as a beautiful subsequence because $$$1 \oplus 1 < 2 \oplus 0$$$.

In the second test case, we can pick elements with indexes $$$1$$$, $$$2$$$ and $$$4$$$ (in $$$0$$$ indexation). For this elements holds: $$$2 \oplus 2 < 4 \oplus 1$$$ and $$$4 \oplus 4 < 1 \oplus 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 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: 3.5 seconds
Memory limit: 256.0 MB

# Problem
Misha has a square $$$n \times n$$$ matrix, where the number in row $$$i$$$ and column $$$j$$$ is equal to $$$a_{i, j}$$$. Misha wants to modify the matrix to contain exactly $$$k$$$ distinct integers. To achieve this goal, Misha can perform the following operation zero or more times:

1. choose any square submatrix of the matrix (you choose $$$(x_1,y_1)$$$, $$$(x_2,y_2)$$$, such that $$$x_1 \leq x_2$$$, $$$y_1 \leq y_2$$$, $$$x_2 - x_1 = y_2 - y_1$$$, then submatrix is a set of cells with coordinates $$$(x, y)$$$, such that $$$x_1 \leq x \leq x_2$$$, $$$y_1 \leq y \leq y_2$$$),
2. choose an integer $$$k$$$, where $$$1 \leq k \leq n^2$$$,
3. replace all integers in the submatrix with $$$k$$$.

Please find the minimum number of operations that Misha needs to achieve his goal.

## Input Format
The first input line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 500, 1 \leq k \leq n^2$$$)  — the size of the matrix and the desired amount of distinct elements in the matrix.

Then $$$n$$$ lines follows. The $$$i$$$-th of them contains $$$n$$$ integers $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}$$$ ($$$1 \leq a_{i,j} \leq n^2$$$) — the elements of the $$$i$$$-th row of the matrix.

## Output Format
Output one integer — the minimum number of operations required.

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

## Note
In the first test case the answer is $$$1$$$, because one can change the value in the bottom right corner of the matrix to $$$1$$$. The resulting matrix can be found below:

111112341

In the second test case the answer is $$$2$$$. First, one can change the entire matrix to contain only $$$1$$$s, and the change the value of any single cell to $$$2$$$. One of the possible resulting matrices is displayed below:

111111112

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
Pak Chanek has a grid that has $$$N$$$ rows and $$$M$$$ columns. Each row is numbered from $$$1$$$ to $$$N$$$ from top to bottom. Each column is numbered from $$$1$$$ to $$$M$$$ from left to right.

Each tile in the grid contains a number. The numbers are arranged as follows:

- Row $$$1$$$ contains integers from $$$1$$$ to $$$M$$$ from left to right.
- Row $$$2$$$ contains integers from $$$M+1$$$ to $$$2 \times M$$$ from left to right.
- Row $$$3$$$ contains integers from $$$2 \times M+1$$$ to $$$3 \times M$$$ from left to right.
- And so on until row $$$N$$$.

A domino is defined as two different tiles in the grid that touch by their sides. A domino is said to be tight if and only if the two numbers in the domino have a difference of exactly $$$1$$$. Count the number of distinct tight dominoes in the grid.

Two dominoes are said to be distinct if and only if there exists at least one tile that is in one domino, but not in the other.

## Input Format
The only line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 10^9$$$) — the number of rows and columns in the grid.

## Output Format
An integer representing the number of distinct tight dominoes in the grid.

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

## Note
The picture below is the grid that Pak Chanek has in the first example.

The picture below is an example of a tight domino in the grid.

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
A basketball competition is held where the number of players in a team does not have a maximum or minimum limit (not necessarily $$$5$$$ players in one team for each match). There are $$$N$$$ candidate players in the competition that will be trained by Pak Chanek, the best basketball coach on earth. The $$$i$$$-th candidate player has a power of $$$P_i$$$.

Pak Chanek will form zero or more teams from the $$$N$$$ candidate players on the condition that each candidate player may only join in at most one team. Each of Pak Chanek's teams will be sent to compete once with an enemy team that has a power of $$$D$$$. In each match, the team sent is said to defeat the enemy team if the sum of powers from the formed players is strictly greater than $$$D$$$.

One of Pak Chanek's skills is that when a team that has been formed plays in a match, he can change the power of each player in the team to be equal to the biggest player power from the team.

Determine the maximum number of wins that can be achieved by Pak Chanek.

## Input Format
The first line contains two integers $$$N$$$ and $$$D$$$ ($$$1 \le N \le 10^5$$$, $$$1 \le D \le 10^9$$$) — the number of candidate players and the power of the enemy team.

The second line contains $$$N$$$ integers $$$P_1, P_2, \ldots, P_N$$$ ($$$1 \le P_i \le 10^9$$$) — the powers of all candidate players.

## Output Format
A line containing an integer representing the maximum number of wins that can be achieved by Pak Chanek.

## Examples
```input
6 180
90 80 70 60 50 100
```
```output
2
```

## Note
The $$$1$$$-st team formed is a team containing players $$$4$$$ and $$$6$$$. The power of each player in the team becomes $$$100$$$. So the total power of the team is $$$100 + 100 = 200 > 180$$$.

The $$$2$$$-nd team formed is a team containing players $$$1$$$, $$$2$$$, and $$$5$$$. The power of each player in the team becomes $$$90$$$. So the total power of the team is $$$90 + 90 + 90 = 270 > 180$$$.

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
Pak Chanek has a mirror in the shape of a circle. There are $$$N$$$ lamps on the circumference numbered from $$$1$$$ to $$$N$$$ in clockwise order. The length of the arc from lamp $$$i$$$ to lamp $$$i+1$$$ is $$$D_i$$$ for $$$1 \leq i \leq N-1$$$. Meanwhile, the length of the arc between lamp $$$N$$$ and lamp $$$1$$$ is $$$D_N$$$.

Pak Chanek wants to colour the lamps with $$$M$$$ different colours. Each lamp can be coloured with one of the $$$M$$$ colours. However, there cannot be three different lamps such that the colours of the three lamps are the same and the triangle made by considering the three lamps as vertices is a right triangle (triangle with one of its angles being exactly $$$90$$$ degrees).

The following are examples of lamp colouring configurations on the circular mirror.

Figure 1. an example of an incorrect colouring because lamps $$$1$$$, $$$2$$$, and $$$3$$$ form a right triangleFigure 2. an example of a correct colouringFigure 3. an example of a correct colouring

Before colouring the lamps, Pak Chanek wants to know the number of distinct colouring configurations he can make. Count the number of distinct possible lamp colouring configurations, modulo $$$998\,244\,353$$$.

## Input Format
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N \le 3 \cdot 10^5$$$, $$$2 \le M \le 3 \cdot 10^5$$$) — the number of lamps in the mirror and the number of different colours used.

The second line contains $$$N$$$ integers $$$D_1, D_2, \ldots, D_N$$$ ($$$1 \le D_i \le 10^9$$$) — the lengths of the arcs between the lamps in the mirror.

## Output Format
An integer representing the number of possible lamp colouring configurations, modulo $$$998\,244\,353$$$.

## Examples
```input
4 2
10 10 6 14
```
```output
10
```
-----
```input
1 2
10
```
```output
2
```

## Note
In the first example, all correct lamp colouring configurations are $$$[1, 1, 2, 1]$$$, $$$[1, 1, 2, 2]$$$, $$$[1, 2, 1, 2]$$$, $$$[1, 2, 2, 1]$$$, $$$[1, 2, 2, 2]$$$, $$$[2, 1, 1, 1]$$$, $$$[2, 1, 1, 2]$$$, $$$[2, 1, 2, 1]$$$, $$$[2, 2, 1, 1]$$$, and $$$[2, 2, 1, 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 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: 128.0 MB

# Problem
Pak Chanek plans to build a garage. He wants the garage to consist of a square and a right triangle that are arranged like the following illustration.

Define $$$a$$$ and $$$b$$$ as the lengths of two of the sides in the right triangle as shown in the illustration. An integer $$$x$$$ is suitable if and only if we can construct a garage with assigning positive integer values for the lengths $$$a$$$ and $$$b$$$ ($$$a<b$$$) so that the area of the square at the bottom is exactly $$$x$$$. As a good friend of Pak Chanek, you are asked to help him find the $$$N$$$-th smallest suitable number.

## Input Format
The only line contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^9$$$).

## Output Format
An integer that represents the $$$N$$$-th smallest suitable number.

## Examples
```input
3
```
```output
7
```

## Note
The $$$3$$$-rd smallest suitable number is $$$7$$$. A square area of $$$7$$$ can be obtained by assigning $$$a=3$$$ and $$$b=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 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
One day, Pak Chanek who is already bored of being alone at home decided to go traveling. While looking for an appropriate place, he found that Londonesia has an interesting structure.

According to the information gathered by Pak Chanek, there are $$$N$$$ cities numbered from $$$1$$$ to $$$N$$$. The cities are connected to each other with $$$N-1$$$ two-directional roads, with the $$$i$$$-th road connecting cities $$$U_i$$$ and $$$V_i$$$, and taking a time of $$$W_i$$$ hours to be traversed. In other words, Londonesia's structure forms a tree.

Pak Chanek wants to go on a journey in Londonesia starting and ending in any city (not necessarily the same city) such that each city is visited at least once with the least time possible. In order for the journey to end quicker, Pak Chanek also carries an instant teleportation device for moving from one city to any city that can only be used at most once. Help Pak Chanek for finding the minimum time needed.

Notes:

- Pak Chanek only needs to visit each city at least once. Pak Chanek does not have to traverse each road.
- In the journey, a city or a road can be visited more than once.

## Input Format
The first line contains a single integer $$$N$$$ ($$$1 \le N \le 10^5$$$) — the number of cities in Londonesia.

The $$$i$$$-th of the next $$$N-1$$$ lines contains three integers $$$U_i$$$, $$$V_i$$$, and $$$W_i$$$ ($$$1 \le U_i, V_i \le N$$$, $$$1 \le W_i \le 10^9$$$) — a two-directional road that connects cities $$$U_i$$$ and $$$V_i$$$ that takes $$$W_i$$$ hours to be traversed. The roads in Londonesia form a tree.

## Output Format
Output one integer, which represents the minimum time in hours that is needed to visit each city at least once.

## Examples
```input
4
1 2 4
2 3 5
3 4 4
```
```output
8
```
-----
```input
5
1 2 45
1 3 50
1 4 10
1 5 65
```
```output
115
```

## Note
In the first example, the journey that has the minimum time is $$$2 → 1 \xrightarrow{\text{teleport}} 4 → 3$$$.

In the second example, the journey that has the minimum time is $$$3 → 1 → 4 → 1 → 2 \xrightarrow{\text{teleport}} 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 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
Pak Chanek is participating in a lemper cooking competition. In the competition, Pak Chanek has to cook lempers with $$$N$$$ stoves that are arranged sequentially from stove $$$1$$$ to stove $$$N$$$. Initially, stove $$$i$$$ has a temperature of $$$A_i$$$ degrees. A stove can have a negative temperature.

Pak Chanek realises that, in order for his lempers to be cooked, he needs to keep the temperature of each stove at a non-negative value. To make it happen, Pak Chanek can do zero or more operations. In one operation, Pak Chanek chooses one stove $$$i$$$ with $$$2 \leq i \leq N-1$$$, then:

1. changes the temperature of stove $$$i-1$$$ into $$$A_{i-1} := A_{i-1} + A_{i}$$$,
2. changes the temperature of stove $$$i+1$$$ into $$$A_{i+1} := A_{i+1} + A_{i}$$$, and
3. changes the temperature of stove $$$i$$$ into $$$A_i := -A_i$$$.

Pak Chanek wants to know the minimum number of operations he needs to do such that the temperatures of all stoves are at non-negative values. Help Pak Chanek by telling him the minimum number of operations needed or by reporting if it is not possible to do.

## Input Format
The first line contains a single integer $$$N$$$ ($$$1 \le N \le 10^5$$$) — the number of stoves.

The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$ ($$$-10^9 \leq A_i \leq 10^9$$$) — the initial temperatures of the stoves.

## Output Format
Output an integer representing the minimum number of operations needed to make the temperatures of all stoves at non-negative values or output $$$-1$$$ if it is not possible.

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

## Note
For the first example, a sequence of operations that can be done is as follows:

- Pak Chanek does an operation to stove $$$3$$$, $$$A = [2, -2, 1, 4, 2, -2, 9]$$$.
- Pak Chanek does an operation to stove $$$2$$$, $$$A = [0, 2, -1, 4, 2, -2, 9]$$$.
- Pak Chanek does an operation to stove $$$3$$$, $$$A = [0, 1, 1, 3, 2, -2, 9]$$$.
- Pak Chanek does an operation to stove $$$6$$$, $$$A = [0, 1, 1, 3, 0, 2, 7]$$$.

There is no other sequence of operations such that the number of operations needed is fewer than $$$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 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
Suppose $$$a_1, a_2, \dots, a_n$$$ is a sorted integer sequence of length $$$n$$$ such that $$$a_1 \leq a_2 \leq \dots \leq a_n$$$.

For every $$$1 \leq i \leq n$$$, the prefix sum $$$s_i$$$ of the first $$$i$$$ terms $$$a_1, a_2, \dots, a_i$$$ is defined by $$$$$$ s_i = \sum_{k=1}^i a_k = a_1 + a_2 + \dots + a_i. $$$$$$

Now you are given the last $$$k$$$ terms of the prefix sums, which are $$$s_{n-k+1}, \dots, s_{n-1}, s_{n}$$$. Your task is to determine whether this is possible.

Formally, given $$$k$$$ integers $$$s_{n-k+1}, \dots, s_{n-1}, s_{n}$$$, the task is to check whether there is a sequence $$$a_1, a_2, \dots, a_n$$$ such that

1. $$$a_1 \leq a_2 \leq \dots \leq a_n$$$, and
2. $$$s_i = a_1 + a_2 + \dots + a_i$$$ for all $$$n-k+1 \leq i \leq n$$$.

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases. The following lines contain the description of each test case.

The first line of each test case contains two integers $$$n$$$ ($$$1 \leq n \leq 10^5$$$) and $$$k$$$ ($$$1 \leq k \leq n$$$), indicating the length of the sequence $$$a$$$ and the number of terms of prefix sums, respectively.

The second line of each test case contains $$$k$$$ integers $$$s_{n-k+1}, \dots, s_{n-1}, s_{n}$$$ ($$$-10^9 \leq s_i \leq 10^9$$$ for every $$$n-k+1 \leq i \leq n$$$).

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

## Output Format
For each test case, output "YES" (without quotes) if it is possible and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).

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

## Note
In the first test case, we have the only sequence $$$a = [1, 1, 1, 1, 1]$$$.

In the second test case, we can choose, for example, $$$a = [-3, -2, -1, 0, 1, 2, 3]$$$.

In the third test case, the prefix sums define the only sequence $$$a = [2, 1, 1]$$$, but it is not sorted.

In the fourth test case, it can be shown that there is no sequence with the given prefix sums.

Now solve the problem and return the code.