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

# Problem
You are given a positive integer $$$n$$$.

The weight of a permutation $$$p_1, p_2, \ldots, p_n$$$ is the number of indices $$$1\le i\le n$$$ such that $$$i$$$ divides $$$p_i$$$. Find a permutation $$$p_1,p_2,\dots, p_n$$$ with the minimum possible weight (among all permutations of length $$$n$$$).

A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^4$$$). The description of the test cases follows.

The only line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the length of permutation.

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

## Output Format
For each test case, print a line containing $$$n$$$ integers $$$p_1, p_2,\dots, p_n$$$ so that the permutation $$$p$$$ has the minimum possible weight.

If there are several possible answers, you can print any of them.

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

## Note
In the first test case, the only valid permutation is $$$p=[1]$$$. Its weight is $$$1$$$.

In the second test case, one possible answer is the permutation $$$p=[2,1,4,3]$$$. One can check that $$$1$$$ divides $$$p_1$$$ and $$$i$$$ does not divide $$$p_i$$$ for $$$i=2,3,4$$$, so the weight of this permutation is $$$1$$$. It is impossible to find a permutation of length $$$4$$$ with a strictly smaller weight.

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
Stanley and Megan decided to shop in the "Crossmarket" grocery store, which can be represented as a matrix with $$$n$$$ rows and $$$m$$$ columns.

Stanley and Megan can move to an adjacent cell using $$$1$$$ unit of power. Two cells are considered adjacent if they share an edge. To speed up the shopping process, Megan brought her portals with her, and she leaves one in each cell she visits (if there is no portal yet). If a person (Stanley or Megan) is in a cell with a portal, that person can use $$$1$$$ unit of power to teleport to any other cell with a portal, including Megan's starting cell.

They decided to split up: Stanley will go from the upper-left cell (cell with coordinates $$$(1, 1)$$$) to the lower-right cell (cell with coordinates $$$(n, m)$$$), whilst Megan needs to get from the lower-left cell (cell with coordinates $$$(n, 1)$$$) to the upper-right cell (cell with coordinates $$$(1, m)$$$).

What is the minimum total energy needed for them both to do that?

Note that they can choose the time they move. Time does not affect energy.

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

The only line in the test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^5$$$).

## Output Format
For each test case print a single integer on a new line – the answer.

## Examples
```input
7
7 5
5 7
1 1
100000 100000
57 228
1 5
5 1
```
```output
15
15
0
299998
340
5
5
```

## Note
In the first test case they can stick to the following plan:

1. Megan (red circle) moves to the cell $$$(7, 3)$$$. Then she goes to the cell $$$(1, 3)$$$, and Stanley (blue circle) does the same.
2. Stanley uses the portal in that cell (cells with portals are grey) to get to the cell $$$(7, 3)$$$. Then he moves to his destination — cell $$$(7, 5)$$$.
3. Megan also finishes her route and goes to the cell $$$(1, 5)$$$.

The total energy spent is $$$(2 + 6) + (2 + 1 + 2) + (2)= 15$$$, which is our final answer.

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

# Problem
The Narrator has an integer array $$$a$$$ of length $$$n$$$, but he will only tell you the size $$$n$$$ and $$$q$$$ statements, each of them being three integers $$$i, j, x$$$, which means that $$$a_i \mid a_j = x$$$, where $$$|$$$ denotes the bitwise OR operation.

Find the lexicographically smallest array $$$a$$$ that satisfies all the statements.

An array $$$a$$$ is lexicographically smaller than an array $$$b$$$ of the same length if and only if the following holds:

- in the first position where $$$a$$$ and $$$b$$$ differ, the array $$$a$$$ has a smaller element than the corresponding element in $$$b$$$.

## Input Format
In the first line you are given with two integers $$$n$$$ and $$$q$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le q \le 2 \cdot 10^5$$$).

In the next $$$q$$$ lines you are given with three integers $$$i$$$, $$$j$$$, and $$$x$$$ ($$$1 \le i, j \le n$$$, $$$0 \le x < 2^{30}$$$) — the statements.

It is guaranteed that all $$$q$$$ statements hold for at least one array.

## Output Format
On a single line print $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^{30}$$$) — array $$$a$$$.

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

## Note
In the first sample, these are all the arrays satisfying the statements:

- $$$[0, 3, 2, 2]$$$,
- $$$[2, 1, 0, 0]$$$,
- $$$[2, 1, 0, 2]$$$,
- $$$[2, 1, 2, 0]$$$,
- $$$[2, 1, 2, 2]$$$,
- $$$[2, 3, 0, 0]$$$,
- $$$[2, 3, 0, 2]$$$,
- $$$[2, 3, 2, 0]$$$,
- $$$[2, 3, 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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Stanley lives in a country that consists of $$$n$$$ cities (he lives in city $$$1$$$). There are bidirectional roads between some of the cities, and you know how long it takes to ride through each of them. Additionally, there is a flight between each pair of cities, the flight between cities $$$u$$$ and $$$v$$$ takes $$$(u - v)^2$$$ time.

Stanley is quite afraid of flying because of watching "Sully: Miracle on the Hudson" recently, so he can take at most $$$k$$$ flights. Stanley wants to know the minimum time of a journey to each of the $$$n$$$ cities from the city $$$1$$$.

## Input Format
In the first line of input there are three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \leq n \leq 10^{5}$$$, $$$1 \leq m \leq 10^{5}$$$, $$$1 \leq k \leq 20$$$) — the number of cities, the number of roads, and the maximal number of flights Stanley can take.

The following $$$m$$$ lines describe the roads. Each contains three integers $$$u$$$, $$$v$$$, $$$w$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$, $$$1 \leq w \leq 10^{9}$$$) — the cities the road connects and the time it takes to ride through. Note that some pairs of cities may be connected by more than one road.

## Output Format
Print $$$n$$$ integers, $$$i$$$-th of which is equal to the minimum time of traveling to city $$$i$$$.

## Examples
```input
3 1 2
1 3 1
```
```output
0 1 1
```
-----
```input
4 3 1
1 2 3
2 4 5
3 4 7
```
```output
0 1 4 6
```
-----
```input
2 1 1
2 1 893746473
```
```output
0 1
```
-----
```input
5 5 2
2 1 33
1 5 93
5 3 48
2 3 21
4 2 1
```
```output
0 1 2 2 3
```

## Note
In the first sample, it takes no time to get to city 1; to get to city 2 it is possible to use a flight between 1 and 2, which will take 1 unit of time; to city 3 you can get via a road from city 1, which will take 1 unit of time.

In the second sample, it also takes no time to get to city 1. To get to city 2 Stanley should use a flight between 1 and 2, which will take 1 unit of time. To get to city 3 Stanley can ride between cities 1 and 2, which will take 3 units of time, and then use a flight between 2 and 3. To get to city 4 Stanley should use a flight between 1 and 2, then take a ride from 2 to 4, which will take 5 units of time.

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a$$$ that contains $$$n$$$ integers. You can choose any proper subsegment $$$a_l, a_{l + 1}, \ldots, a_r$$$ of this array, meaning you can choose any two integers $$$1 \le l \le r \le n$$$, where $$$r - l + 1 < n$$$. We define the beauty of a given subsegment as the value of the following expression:

$$$$$$\max(a_{1}, a_{2}, \ldots, a_{l-1}, a_{r+1}, a_{r+2}, \ldots, a_{n}) - \min(a_{1}, a_{2}, \ldots, a_{l-1}, a_{r+1}, a_{r+2}, \ldots, a_{n}) + \max(a_{l}, \ldots, a_{r}) - \min(a_{l}, \ldots, a_{r}).$$$$$$

Please find the maximum beauty among all proper subsegments.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. Then follow the descriptions of each test case.

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_{i} \leq 10^9$$$) — the elements of the given array.

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

## Output Format
For each testcase print a single integer — the maximum beauty of a proper subsegment.

## Examples
```input
4
8
1 2 2 3 1 5 6 1
5
1 2 3 100 200
4
3 3 3 3
6
7 8 3 1 1 8
```
```output
9
297
0
14
```

## Note
In the first test case, the optimal segment is $$$l = 7$$$, $$$r = 8$$$. The beauty of this segment equals to $$$(6 - 1) + (5 - 1) = 9$$$.

In the second test case, the optimal segment is $$$l = 2$$$, $$$r = 4$$$. The beauty of this segment equals $$$(100 - 2) + (200 - 1) = 297$$$.

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a matrix consisting of $$$n$$$ rows and $$$m$$$ columns. Each cell of this matrix contains $$$0$$$ or $$$1$$$.

Let's call a square of size $$$2 \times 2$$$ without one corner cell an L-shape figure. In one operation you can take one L-shape figure, with at least one cell containing $$$1$$$ and replace all numbers in it with zeroes.

Find the maximum number of operations that you can do with the given matrix.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n, m \leq 500$$$) — the size of the matrix.

Each of the following $$$n$$$ lines contains a binary string of length $$$m$$$ — the description of the matrix.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases does not exceed $$$1000$$$.

## Output Format
For each test case output the maximum number of operations you can do with the given matrix.

## Examples
```input
4
4 3
101
111
011
110
3 4
1110
0111
0111
2 2
00
00
2 2
11
11
```
```output
8
9
0
2
```

## Note
In the first testcase one of the optimal sequences of operations is the following (bold font shows l-shape figure on which operation was performed):

- Matrix before any operation was performed:  101111011110
- Matrix after $$$1$$$ operation was performed:  100101011110
- Matrix after $$$2$$$ operations were performed:  100100011110
- Matrix after $$$3$$$ operations were performed:  100100010110
- Matrix after $$$4$$$ operations were performed:  100000010110
- Matrix after $$$5$$$ operations were performed:  100000010100
- Matrix after $$$6$$$ operations were performed:  100000000100
- Matrix after $$$7$$$ operations were performed:  000000000100
- Matrix after $$$8$$$ operations were performed:  000000000000

In the third testcase from the sample we can not perform any operation because the matrix doesn't contain any ones.

In the fourth testcase it does not matter which L-shape figure we pick in our first operation. We will always be left with single one. So we will perform $$$2$$$ operations.

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
It is the easy version of the problem. The only difference is that in this version $$$a_i \le 200$$$.

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 200$$$) — 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 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
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 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.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.