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
Some number of people (this number is even) have stood in a circle. The people stand in the circle evenly. They are numbered clockwise starting from a person with the number $$$1$$$. Each person is looking through the circle's center at the opposite person.

A sample of a circle of $$$6$$$ persons. The orange arrows indicate who is looking at whom.

You don't know the exact number of people standing in the circle (but this number is even, no doubt). It is known that the person with the number $$$a$$$ is looking at the person with the number $$$b$$$ (and vice versa, of course). What is the number associated with a person being looked at by the person with the number $$$c$$$? If, for the specified $$$a$$$, $$$b$$$, and $$$c$$$, no such circle exists, output -1.

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

Each test case consists of one line containing three distinct integers $$$a$$$, $$$b$$$, $$$c$$$ ($$$1 \le a,b,c \le 10^8$$$).

## Output Format
For each test case output in a separate line a single integer $$$d$$$ — the number of the person being looked at by the person with the number $$$c$$$ in a circle such that the person with the number $$$a$$$ is looking at the person with the number $$$b$$$. If there are multiple solutions, print any of them. Output $$$-1$$$ if there's no circle meeting the given conditions.

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

## Note
In the first test case, there's a desired circle of $$$8$$$ people. The person with the number $$$6$$$ will look at the person with the number $$$2$$$ and the person with the number $$$8$$$ will look at the person with the number $$$4$$$.

In the second test case, there's no circle meeting the conditions. If the person with the number $$$2$$$ is looking at the person with the number $$$3$$$, the circle consists of $$$2$$$ people because these persons are neighbors. But, in this case, they must have the numbers $$$1$$$ and $$$2$$$, but it doesn't meet the problem's conditions.

In the third test case, the only circle with the persons with the numbers $$$2$$$ and $$$4$$$ looking at each other consists of $$$4$$$ people. Therefore, the person with the number $$$10$$$ doesn't occur in the circle.

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
Polycarp has found a table having an infinite number of rows and columns. The rows are numbered from $$$1$$$, starting from the topmost one. The columns are numbered from $$$1$$$, starting from the leftmost one.

Initially, the table hasn't been filled and Polycarp wants to fix it. He writes integers from $$$1$$$ and so on to the table as follows.

The figure shows the placement of the numbers from $$$1$$$ to $$$10$$$. The following actions are denoted by the arrows.

The leftmost topmost cell of the table is filled with the number $$$1$$$. Then he writes in the table all positive integers beginning from $$$2$$$ sequentially using the following algorithm.

First, Polycarp selects the leftmost non-filled cell in the first row and fills it. Then, while the left neighbor of the last filled cell is filled, he goes down and fills the next cell. So he goes down until the last filled cell has a non-filled neighbor to the left (look at the vertical arrow going down in the figure above).

After that, he fills the cells from the right to the left until he stops at the first column (look at the horizontal row in the figure above). Then Polycarp selects the leftmost non-filled cell in the first row, goes down, and so on.

A friend of Polycarp has a favorite number $$$k$$$. He wants to know which cell will contain the number. Help him to find the indices of the row and the column, such that the intersection of the row and the column is the cell containing the number $$$k$$$.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case consists of one line containing one integer $$$k$$$ ($$$1 \le k \le 10^9$$$) which location must be found.

## Output Format
For each test case, output in a separate line two integers $$$r$$$ and $$$c$$$ ($$$r, c \ge 1$$$) separated by spaces — the indices of the row and the column containing the cell filled by the number $$$k$$$, respectively.

## Examples
```input
7
11
14
5
4
1
2
1000000000
```
```output
2 4
4 3
1 3
2 1
1 1
1 2
31623 14130
```

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
Polycarp has a string $$$s$$$. Polycarp performs the following actions until the string $$$s$$$ is empty ($$$t$$$ is initially an empty string):

- he adds to the right to the string $$$t$$$ the string $$$s$$$, i.e. he does $$$t = t + s$$$, where $$$t + s$$$ is a concatenation of the strings $$$t$$$ and $$$s$$$;
- he selects an arbitrary letter of $$$s$$$ and removes from $$$s$$$ all its occurrences (the selected letter must occur in the string $$$s$$$ at the moment of performing this action).

Polycarp performs this sequence of actions strictly in this order.

Note that after Polycarp finishes the actions, the string $$$s$$$ will be empty and the string $$$t$$$ will be equal to some value (that is undefined and depends on the order of removing).

E.g. consider $$$s$$$="abacaba" so the actions may be performed as follows:

- $$$t$$$="abacaba", the letter 'b' is selected, then $$$s$$$="aacaa";
- $$$t$$$="abacabaaacaa", the letter 'a' is selected, then $$$s$$$="c";
- $$$t$$$="abacabaaacaac", the letter 'c' is selected, then $$$s$$$="" (the empty string).

You need to restore the initial value of the string $$$s$$$ using only the final value of $$$t$$$ and find the order of removing letters from $$$s$$$.

## Input Format
The first line contains one integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases. Then $$$T$$$ test cases follow.

Each test case contains one string $$$t$$$ consisting of lowercase letters of the Latin alphabet. The length of $$$t$$$ doesn't exceed $$$5 \cdot 10^5$$$. The sum of lengths of all strings $$$t$$$ in the test cases doesn't exceed $$$5 \cdot 10^5$$$.

## Output Format
For each test case output in a separate line:

- $$$-1$$$, if the answer doesn't exist;
- two strings separated by spaces. The first one must contain a possible initial value of $$$s$$$. The second one must contain a sequence of letters — it's in what order one needs to remove letters from $$$s$$$ to make the string $$$t$$$. E.g. if the string "bac" is outputted, then, first, all occurrences of the letter 'b' were deleted, then all occurrences of 'a', and then, finally, all occurrences of 'c'. If there are multiple solutions, print any one.

## Examples
```input
7
abacabaaacaac
nowyouknowthat
polycarppoycarppoyarppyarppyrpprppp
isi
everywherevrywhrvryhrvrhrvhv
haaha
qweqeewew
```
```output
abacaba bac
-1
polycarp lcoayrp
is si
everywhere ewyrhv
-1
-1
```

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

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
It is a simplified version of problem F2. The difference between them is the constraints (F1: $$$k \le 2$$$, F2: $$$k \le 10$$$).

You are given an integer $$$n$$$. Find the minimum integer $$$x$$$ such that $$$x \ge n$$$ and the number $$$x$$$ is $$$k$$$-beautiful.

A number is called $$$k$$$-beautiful if its decimal representation having no leading zeroes contains no more than $$$k$$$ different digits. E.g. if $$$k = 2$$$, the numbers $$$3434443$$$, $$$55550$$$, $$$777$$$ and $$$21$$$ are $$$k$$$-beautiful whereas the numbers $$$120$$$, $$$445435$$$ and $$$998244353$$$ are not.

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

Each test case consists of one line containing two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le k \le 2$$$).

## Output Format
For each test case output on a separate line $$$x$$$ — the minimum $$$k$$$-beautiful integer such that $$$x \ge n$$$.

## Examples
```input
4
1 1
221 2
177890 2
998244353 1
```
```output
1
221
181111
999999999
```

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 playing a game on a $$$n \times m$$$ grid, in which the computer has selected some cell $$$(x, y)$$$ of the grid, and you have to determine which one.

To do so, you will choose some $$$k$$$ and some $$$k$$$ cells $$$(x_1, y_1),\, (x_2, y_2), \ldots, (x_k, y_k)$$$, and give them to the computer. In response, you will get $$$k$$$ numbers $$$b_1,\, b_2, \ldots b_k$$$, where $$$b_i$$$ is the manhattan distance from $$$(x_i, y_i)$$$ to the hidden cell $$$(x, y)$$$ (so you know which distance corresponds to which of $$$k$$$ input cells).

After receiving these $$$b_1,\, b_2, \ldots, b_k$$$, you have to be able to determine the hidden cell. What is the smallest $$$k$$$ for which is it possible to always guess the hidden cell correctly, no matter what cell computer chooses?

As a reminder, the manhattan distance between cells $$$(a_1, b_1)$$$ and $$$(a_2, b_2)$$$ is equal to $$$|a_1-a_2|+|b_1-b_2|$$$.

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

The single line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^9$$$) — the number of rows and the number of columns in the grid.

## Output Format
For each test case print a single integer — the minimum $$$k$$$ for that test case.

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

## Note
In the first test case, the smallest such $$$k$$$ is $$$2$$$, for which you can choose, for example, cells $$$(1, 1)$$$ and $$$(2, 1)$$$.

Note that you can't choose cells $$$(1, 1)$$$ and $$$(2, 3)$$$ for $$$k = 2$$$, as both cells $$$(1, 2)$$$ and $$$(2, 1)$$$ would give $$$b_1 = 1, b_2 = 2$$$, so we wouldn't be able to determine which cell is hidden if computer selects one of those.

In the second test case, you should choose $$$k = 1$$$, for it you can choose cell $$$(3, 1)$$$ or $$$(1, 1)$$$.

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
An array $$$[b_1, b_2, \ldots, b_m]$$$ is a palindrome, if $$$b_i = b_{m+1-i}$$$ for each $$$i$$$ from $$$1$$$ to $$$m$$$. Empty array is also a palindrome.

An array is called kalindrome, if the following condition holds:

- It's possible to select some integer $$$x$$$ and delete some of the elements of the array equal to $$$x$$$, so that the remaining array (after gluing together the remaining parts) is a palindrome.

Note that you don't have to delete all elements equal to $$$x$$$, and you don't have to delete at least one element equal to $$$x$$$.

For example :

- $$$[1, 2, 1]$$$ is kalindrome because you can simply not delete a single element.
- $$$[3, 1, 2, 3, 1]$$$ is kalindrome because you can choose $$$x = 3$$$ and delete both elements equal to $$$3$$$, obtaining array $$$[1, 2, 1]$$$, which is a palindrome.
- $$$[1, 2, 3]$$$ is not kalindrome.

You are given an array $$$[a_1, a_2, \ldots, a_n]$$$. Determine if $$$a$$$ is kalindrome or not.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 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 \le a_i \le n$$$) — elements of the array.

It's guaranteed that the sum of $$$n$$$ over all test cases won't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print YES if $$$a$$$ is kalindrome and NO otherwise. You can print each letter in any case.

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

## Note
In the first test case, array $$$[1]$$$ is already a palindrome, so it's a kalindrome as well.

In the second test case, we can choose $$$x = 2$$$, delete the second element, and obtain array $$$[1]$$$, which is a palindrome.

In the third test case, it's impossible to obtain a palindrome.

In the fourth test case, you can choose $$$x = 4$$$ and delete the fifth element, obtaining $$$[1, 4, 4, 1]$$$. You also can choose $$$x = 1$$$, delete the first and the fourth elements, and obtain $$$[4, 4, 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 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
Lee couldn't sleep lately, because he had nightmares. In one of his nightmares (which was about an unbalanced global round), he decided to fight back and propose a problem below (which you should solve) to balance the round, hopefully setting him free from the nightmares.

A non-empty array $$$b_1, b_2, \ldots, b_m$$$ is called good, if there exist $$$m$$$ integer sequences which satisfy the following properties:

- The $$$i$$$-th sequence consists of $$$b_i$$$ consecutive integers (for example if $$$b_i = 3$$$ then the $$$i$$$-th sequence can be $$$(-1, 0, 1)$$$ or $$$(-5, -4, -3)$$$ but not $$$(0, -1, 1)$$$ or $$$(1, 2, 3, 4)$$$).
- Assuming the sum of integers in the $$$i$$$-th sequence is $$$sum_i$$$, we want $$$sum_1 + sum_2 + \ldots + sum_m$$$ to be equal to $$$0$$$.

You are given an array $$$a_1, a_2, \ldots, a_n$$$. It has $$$2^n - 1$$$ nonempty subsequences. Find how many of them are good.

As this number can be very large, output it modulo $$$10^9 + 7$$$.

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

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

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

## Output Format
Print a single integer — the number of nonempty good subsequences of $$$a$$$, modulo $$$10^9 + 7$$$.

## Examples
```input
4
2 2 4 7
```
```output
10
```
-----
```input
10
12391240 103904 1000000000 4142834 12039 142035823 1032840 49932183 230194823 984293123
```
```output
996
```

## Note
For the first test, two examples of good subsequences are $$$[2, 7]$$$ and $$$[2, 2, 4, 7]$$$:

For $$$b = [2, 7]$$$ we can use $$$(-3, -4)$$$ as the first sequence and $$$(-2, -1, \ldots, 4)$$$ as the second. Note that subsequence $$$[2, 7]$$$ appears twice in $$$[2, 2, 4, 7]$$$, so we have to count it twice.

Green circles denote $$$(-3, -4)$$$ and orange squares denote $$$(-2, -1, \ldots, 4)$$$.

For $$$b = [2, 2, 4, 7]$$$ the following sequences would satisfy the properties: $$$(-1, 0)$$$, $$$(-3, -2)$$$, $$$(0, 1, 2, 3)$$$ and $$$(-3, -2, \ldots, 3)$$$

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Lee was planning to get closer to Mashtali's heart to proceed with his evil plan(which we're not aware of, yet), so he decided to beautify Mashtali's graph. But he made several rules for himself. And also he was too busy with his plans that he didn't have time for such minor tasks, so he asked you for help.

Mashtali's graph is an undirected weighted graph with $$$n$$$ vertices and $$$m$$$ edges with weights equal to either $$$1$$$ or $$$2$$$. Lee wants to direct the edges of Mashtali's graph so that it will be as beautiful as possible.

Lee thinks that the beauty of a directed weighted graph is equal to the number of its Oddysey vertices. A vertex $$$v$$$ is an Oddysey vertex if $$$|d^+(v) - d^-(v)| = 1$$$, where $$$d^+(v)$$$ is the sum of weights of the outgoing from $$$v$$$ edges, and $$$d^-(v)$$$ is the sum of the weights of the incoming to $$$v$$$ edges.

Find the largest possible beauty of a graph that Lee can achieve by directing the edges of Mashtali's graph. In addition, find any way to achieve it.

Note that you have to orient each edge.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \le n \le 10^5;\; 1 \le m \le 10^5)$$$ — the numbers of vertices and edges in the graph.

The $$$i$$$-th line of the following $$$m$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$ and $$$w_i$$$ $$$( 1 \le u_i , v_i \le n;\; u_i \neq v_i;\; \bf{w_i \in \{1, 2\}} )$$$ — the endpoints of the $$$i$$$-th edge and its weight.

Note that the graph doesn't have to be connected, and it might contain multiple edges.

## Output Format
In the first line print a single integer — the maximum beauty of the graph Lee can achieve.

In the second line print a string of length $$$m$$$ consisting of $$$1$$$s and $$$2$$$s — directions of the edges.

If you decide to direct the $$$i$$$-th edge from vertex $$$u_i$$$ to vertex $$$v_i$$$, $$$i$$$-th character of the string should be $$$1$$$. Otherwise, it should be $$$2$$$.

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

## Note
Explanation for the first sample:

vertices $$$2$$$ and $$$5$$$ are Oddyseys.

Explanation for the third sample:

vertices $$$1$$$ and $$$6$$$ are Oddyseys.

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
Right before the UEFA Euro 2020, AmShZ and Safar placed bets on who'd be the champion, AmShZ betting on Italy, and Safar betting on France.

Of course, AmShZ won. Hence, Safar gave him a bracket sequence $$$S$$$. Note that a bracket sequence is a string made of '(' and ')' characters.

AmShZ can perform the following operation any number of times:

- First, he cuts his string $$$S$$$ into three (possibly empty) contiguous substrings $$$A, B$$$ and $$$C$$$. Then, he glues them back by using a '(' and a ')' characters, resulting in a new string $$$S$$$ = $$$A$$$ + "(" + $$$B$$$ + ")" + $$$C$$$.For example, if $$$S$$$ = "))((" and AmShZ cuts it into $$$A$$$ = "", $$$B$$$ = "))", and $$$C$$$ = "((", He will obtain $$$S$$$ = "()))((" as a new string.

After performing some (possibly none) operations, AmShZ gives his string to Keshi and asks him to find the initial string. Of course, Keshi might be able to come up with more than one possible initial string. Keshi is interested in finding the lexicographically smallest possible initial string.

Your task is to help Keshi in achieving his goal.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

## Input Format
The only line of input contains a single string $$$S$$$ — the string after the operations $$$(1\le |S|\le 3 \cdot 10^5)$$$.

It is guaranteed that the first character of $$$S$$$ is ')'.

## Output Format
Print the lexicographically smallest possible initial string before operations.

## Examples
```input
)(()(())))
```
```output
)((())))
```

## Note
In the first sample, you can transform ")((())))" into ")(()(())))" by splitting it into ")(", empty string, and "(())))". It can be shown that this is the lexicographically smallest possible initial string

Now solve the problem and return the code.