apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
A bracket sequence is a string containing only characters "(" and ")". A regular bracket sequence (or, shortly, an RBS) is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example:

- bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)");
- bracket sequences ")(", "(" and ")" are not.

There was an RBS. Some brackets have been replaced with question marks. Is it true that there is a unique way to replace question marks with brackets, so that the resulting sequence is an RBS?

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

The only line of each testcase contains an RBS with some brackets replaced with question marks. Each character is either '(', ')' or '?'. At least one RBS can be recovered from the given sequence.

The total length of the sequences over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each testcase, print "YES" if the way to replace question marks with brackets, so that the resulting sequence is an RBS, is unique. If there is more than one way, then print "NO".

## Examples
```input
5
(?))
??????
()
??
?(?)()?)
```
```output
YES
NO
YES
YES
NO
```

## Note
In the first testcase, the only possible original RBS is "(())".

In the second testcase, there are multiple ways to recover an RBS.

In the third and the fourth testcases, the only possible original RBS is "()".

In the fifth testcase, the original RBS can be either "((()()))" or "(())()()".

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

# Problem
You are given a tree consisting of $$$n$$$ vertices. A number is written on each vertex; the number on vertex $$$i$$$ is equal to $$$a_i$$$.

Recall that a simple path is a path that visits each vertex at most once. Let the weight of the path be the bitwise XOR of the values written on vertices it consists of. Let's say that a tree is good if no simple path has weight $$$0$$$.

You can apply the following operation any number of times (possibly, zero): select a vertex of the tree and replace the value written on it with an arbitrary positive integer. What is the minimum number of times you have to apply this operation in order to make the tree good?

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of vertices.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i < 2^{30}$$$) — the numbers written on vertices.

Then $$$n - 1$$$ lines follow, each containing two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le n; x \ne y$$$) denoting an edge connecting vertex $$$x$$$ with vertex $$$y$$$. It is guaranteed that these edges form a tree.

## Output Format
Print a single integer — the minimum number of times you have to apply the operation in order to make the tree good.

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

## Note
In the first example, it is enough to replace the value on the vertex $$$1$$$ with $$$13$$$, and the value on the vertex $$$4$$$ with $$$42$$$.

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

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Vlad, like everyone else, loves to sleep very much.

Every day Vlad has to do $$$n$$$ things, each at a certain time. For each of these things, he has an alarm clock set, the $$$i$$$-th of them is triggered on $$$h_i$$$ hours $$$m_i$$$ minutes every day ($$$0 \le h_i < 24, 0 \le m_i < 60$$$). Vlad uses the $$$24$$$-hour time format, so after $$$h=12, m=59$$$ comes $$$h=13, m=0$$$ and after $$$h=23, m=59$$$ comes $$$h=0, m=0$$$.

This time Vlad went to bed at $$$H$$$ hours $$$M$$$ minutes ($$$0 \le H < 24, 0 \le M < 60$$$) and asks you to answer: how much he will be able to sleep until the next alarm clock.

If any alarm clock rings at the time when he went to bed, then he will sleep for a period of time of length $$$0$$$.

## Input Format
The first line of input data contains an integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases in the test.

The first line of the case contains three integers $$$n$$$, $$$H$$$ and $$$M$$$ ($$$1 \le n \le 10, 0 \le H < 24, 0 \le M < 60$$$) — the number of alarms and the time Vlad went to bed.

The following $$$n$$$ lines contain two numbers each $$$h_i$$$ and $$$m_i$$$ ($$$0 \le h_i < 24, 0 \le m_i < 60$$$) — the time of the $$$i$$$ alarm. It is acceptable that two or more alarms will trigger at the same time.

Numbers describing time do not contain leading zeros.

## Output Format
Output $$$t$$$ lines, each containing the answer to the corresponding test case. As an answer, output two numbers  — the number of hours and minutes that Vlad will sleep, respectively. If any alarm clock rings at the time when he went to bed, the answer will be 0 0.

## Examples
```input
3
1 6 13
8 0
3 6 0
12 30
14 45
6 0
2 23 35
20 15
10 30
```
```output
1 47
0 0
10 55
```

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

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarp was presented with some sequence of integers $$$a$$$ of length $$$n$$$ ($$$1 \le a_i \le n$$$). A sequence can make Polycarp happy only if it consists of different numbers (i.e. distinct numbers).

In order to make his sequence like this, Polycarp is going to make some (possibly zero) number of moves.

In one move, he can:

- remove the first (leftmost) element of the sequence.

For example, in one move, the sequence $$$[3, 1, 4, 3]$$$ will produce the sequence $$$[1, 4, 3]$$$, which consists of different numbers.

Determine the minimum number of moves he needs to make so that in the remaining sequence all elements are different. In other words, find the length of the smallest prefix of the given sequence $$$a$$$, after removing which all values in the sequence will be unique.

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

Each test case consists of two lines.

The first line contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the given sequence $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — elements of the given sequence $$$a$$$.

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

## Output Format
For each test case print your answer on a separate line — the minimum number of elements that must be removed from the beginning of the sequence so that all remaining elements are different.

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

## Note
The following are the sequences that will remain after the removal of prefixes:

- $$$[1, 4, 3]$$$;
- $$$[1]$$$;
- $$$[1]$$$;
- $$$[6, 5, 4, 3, 2, 1]$$$;
- $$$[2, 1]$$$.

It is easy to see that all the remaining sequences contain only distinct elements. In each test case, the shortest matching prefix was removed.

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
Find the minimum number with the given sum of digits $$$s$$$ such that all digits in it are distinct (i.e. all digits are unique).

For example, if $$$s=20$$$, then the answer is $$$389$$$. This is the minimum number in which all digits are different and the sum of the digits is $$$20$$$ ($$$3+8+9=20$$$).

For the given $$$s$$$ print the required number.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 45$$$) — the number of test cases.

Each test case is specified by a line that contains the only integer $$$s$$$ ($$$1 \le s \le 45$$$).

## Output Format
Print $$$t$$$ integers — the answers to the given test cases.

## Examples
```input
4
20
8
45
10
```
```output
389
8
123456789
19
```

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

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
A tree is a connected undirected graph without cycles. Note that in this problem, we are talking about not rooted trees.

You are given four positive integers $$$n, d_{12}, d_{23}$$$ and $$$d_{31}$$$. Construct a tree such that:

- it contains $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$,
- the distance (length of the shortest path) from vertex $$$1$$$ to vertex $$$2$$$ is $$$d_{12}$$$,
- distance from vertex $$$2$$$ to vertex $$$3$$$ is $$$d_{23}$$$,
- the distance from vertex $$$3$$$ to vertex $$$1$$$ is $$$d_{31}$$$.

Output any tree that satisfies all the requirements above, or determine that no such tree exists.

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

This is followed by $$$t$$$ test cases, each written on a separate line.

Each test case consists of four positive integers $$$n, d_{12}, d_{23}$$$ and $$$d_{31}$$$ ($$$3 \le n \le 2\cdot10^5; 1 \le d_{12}, d_{23}, d_{31} \le n-1$$$).

It is guaranteed that the sum of $$$n$$$ values for all test cases does not exceed $$$2\cdot10^5$$$.

## Output Format
For each test case, print YES if the suitable tree exists, and NO otherwise.

If the answer is positive, print another $$$n-1$$$ line each containing a description of an edge of the tree — a pair of positive integers $$$x_i, y_i$$$, which means that the $$$i$$$th edge connects vertices $$$x_i$$$ and $$$y_i$$$.

The edges and vertices of the edges can be printed in any order. If there are several suitable trees, output any of them.

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

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