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
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 c++17.

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

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

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are given 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 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
Rhodoks has a tree with $$$n$$$ vertices, but he doesn't remember its structure. The vertices are indexed from $$$1$$$ to $$$n$$$.

A segment $$$[l,r]$$$ ($$$1 \leq l \leq r \leq n$$$) is good if the vertices with indices $$$l$$$, $$$l + 1$$$, ..., $$$r$$$ form a connected component in Rhodoks' tree. Otherwise, it is bad.

For example, if the tree is the one in the picture, then only the segment $$$[3,4]$$$ is bad while all the other segments are good.

For each of the $$$\frac{n(n+1)}{2}$$$ segments, Rhodoks remembers whether it is good or bad. Can you help him recover the tree? If there are multiple solutions, print any.

It is guaranteed that the there is at least one tree satisfying Rhodoks' description.

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2000$$$) — the number of vertices in the tree.

Then $$$n$$$ lines follow. The $$$i$$$-th of these lines contains a string $$$good_i$$$ of length $$$n+1-i$$$ consisting of 0 and 1. If the segment $$$[i,i+j-1]$$$ is good then the $$$j$$$-th character of $$$good_i$$$ is 1, otherwise $$$j$$$-th character of $$$good_i$$$ is 0.

It is guaranteed that the there is at least one tree consistent with the given data.

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

## Output Format
For each test case, print $$$n-1$$$ lines describing the tree you recover.

The $$$i$$$-th line should contain two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i,v_i \leq n$$$), denoting an edge between vertices $$$u_i$$$ and $$$v_i$$$.

If there are multiple solutions, print any.

## Examples
```input
3
4
1111
111
10
1
6
111111
11111
1111
111
11
1
12
100100000001
11100000001
1000000000
100000000
10010001
1110000
100000
10000
1001
111
10
1
```
```output
1 2
2 3
2 4
1 2
2 3
3 4
4 5
5 6
2 3
6 7
10 11
2 4
6 8
10 12
1 4
5 8
9 12
5 12
2 12
```

## Note
The first test case is explained in the statement.

In the second test case, one possible tree is as follows:

In the third test case, one possible tree is as follows:

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
You are given two arrays of integers $$$a_1,a_2,\dots,a_n$$$ and $$$b_1,b_2,\dots,b_m$$$.

Alice and Bob are going to play a game. Alice moves first and they take turns making a move.

They play on a grid of size $$$n \times m$$$ (a grid with $$$n$$$ rows and $$$m$$$ columns). Initially, there is a rook positioned on the first row and first column of the grid.

During her/his move, a player can do one of the following two operations:

1. Move the rook to a different cell on the same row or the same column of the current cell. A player cannot move the rook to a cell that has been visited $$$1000$$$ times before (i.e., the rook can stay in a certain cell at most $$$1000$$$ times during the entire game). Note that the starting cell is considered to be visited once at the beginning of the game.
2. End the game immediately with a score of $$$a_r+b_c$$$, where $$$(r, c)$$$ is the current cell (i.e., the rook is on the $$$r$$$-th row and $$$c$$$-th column).

Bob wants to maximize the score while Alice wants to minimize it. If they both play this game optimally, what is the final score of the game?

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n,m \leq 2 \cdot 10^5$$$) — the length of the arrays $$$a$$$ and $$$b$$$ (which coincide with the number of rows and columns of the grid).

The second line contains the $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 5 \cdot 10^8$$$).

The third line contains the $$$m$$$ integers $$$b_1, b_2,\dots, b_n$$$ ($$$1 \leq b_i \leq 5 \cdot 10^8$$$).

## Output Format
Print a single line containing the final score of the game.

## Examples
```input
2 1
3 2
2
```
```output
4
```
-----
```input
4 5
235499701 451218171 355604420 132973458
365049318 264083156 491406845 62875547 175951751
```
```output
531556171
```

## Note
In the first test case, Alice moves the rook to $$$(2, 1)$$$ and Bob moves the rook to $$$(1, 1)$$$. This process will repeat for $$$999$$$ times until finally, after Alice moves the rook, Bob cannot move it back to $$$(1, 1)$$$ because it has been visited $$$1000$$$ times before. So the final score of the game is $$$a_2+b_1=4$$$.

In the second test case, the final score of the game is $$$a_3+b_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
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 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
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 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
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 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
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 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
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 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
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.