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
Monocarp is playing a computer game. Now he wants to complete the first level of this game.

A level is a rectangular grid of $$$2$$$ rows and $$$n$$$ columns. Monocarp controls a character, which starts in cell $$$(1, 1)$$$ — at the intersection of the $$$1$$$-st row and the $$$1$$$-st column.

Monocarp's character can move from one cell to another in one step if the cells are adjacent by side and/or corner. Formally, it is possible to move from cell $$$(x_1, y_1)$$$ to cell $$$(x_2, y_2)$$$ in one step if $$$|x_1 - x_2| \le 1$$$ and $$$|y_1 - y_2| \le 1$$$. Obviously, it is prohibited to go outside the grid.

There are traps in some cells. If Monocarp's character finds himself in such a cell, he dies, and the game ends.

To complete a level, Monocarp's character should reach cell $$$(2, n)$$$ — at the intersection of row $$$2$$$ and column $$$n$$$.

Help Monocarp determine if it is possible to complete the level.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Then the test cases follow. Each test case consists of three lines.

The first line contains a single integer $$$n$$$ ($$$3 \le n \le 100$$$) — the number of columns.

The next two lines describe the level. The $$$i$$$-th of these lines describes the $$$i$$$-th line of the level — the line consists of the characters '0' and '1'. The character '0' corresponds to a safe cell, the character '1' corresponds to a trap cell.

Additional constraint on the input: cells $$$(1, 1)$$$ and $$$(2, n)$$$ are safe.

## Output Format
For each test case, output YES if it is possible to complete the level, and NO otherwise.

## Examples
```input
4
3
000
000
4
0011
1100
4
0111
1110
6
010101
101010
```
```output
YES
YES
NO
YES
```

## Note
Consider the example from the statement.

In the first test case, one of the possible paths is $$$(1, 1) \rightarrow (2, 2) \rightarrow (2, 3)$$$.

In the second test case, one of the possible paths is $$$(1, 1) \rightarrow (1, 2) \rightarrow (2, 3) \rightarrow (2, 4)$$$.

In the fourth test case, one of the possible paths is $$$(1, 1) \rightarrow (2, 2) \rightarrow (1, 3) \rightarrow (2, 4) \rightarrow (1, 5) \rightarrow (2, 6)$$$.

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
Monocarp is the coach of the Berland State University programming teams. He decided to compose a problemset for a training session for his teams.

Monocarp has $$$n$$$ problems that none of his students have seen yet. The $$$i$$$-th problem has a topic $$$a_i$$$ (an integer from $$$1$$$ to $$$n$$$) and a difficulty $$$b_i$$$ (an integer from $$$1$$$ to $$$n$$$). All problems are different, that is, there are no two tasks that have the same topic and difficulty at the same time.

Monocarp decided to select exactly $$$3$$$ problems from $$$n$$$ problems for the problemset. The problems should satisfy at least one of two conditions (possibly, both):

- the topics of all three selected problems are different;
- the difficulties of all three selected problems are different.

Your task is to determine the number of ways to select three problems for the problemset.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 50000$$$) — the number of testcases.

The first line of each testcase contains an integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — the number of problems that Monocarp have.

In the $$$i$$$-th of the following $$$n$$$ lines, there are two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — the topic and the difficulty of the $$$i$$$-th problem.

It is guaranteed that there are no two problems that have the same topic and difficulty at the same time.

The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
Print the number of ways to select three training problems that meet either of the requirements described in the statement.

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

## Note
In the first example, you can take the following sets of three problems:

- problems $$$1$$$, $$$2$$$, $$$4$$$;
- problems $$$1$$$, $$$3$$$, $$$4$$$;
- problems $$$2$$$, $$$3$$$, $$$4$$$.

Thus, the number of ways is equal to three.

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
You are given a matrix, consisting of $$$n$$$ rows and $$$m$$$ columns. The rows are numbered top to bottom, the columns are numbered left to right.

Each cell of the matrix can be either free or locked.

Let's call a path in the matrix a staircase if it:

- starts and ends in the free cell;
- visits only free cells;
- has one of the two following structures:   the second cell is $$$1$$$ to the right from the first one, the third cell is $$$1$$$ to the bottom from the second one, the fourth cell is $$$1$$$ to the right from the third one, and so on;  the second cell is $$$1$$$ to the bottom from the first one, the third cell is $$$1$$$ to the right from the second one, the fourth cell is $$$1$$$ to the bottom from the third one, and so on.

In particular, a path, consisting of a single cell, is considered to be a staircase.

Here are some examples of staircases:

Initially all the cells of the matrix are free.

You have to process $$$q$$$ queries, each of them flips the state of a single cell. So, if a cell is currently free, it makes it locked, and if a cell is currently locked, it makes it free.

Print the number of different staircases after each query. Two staircases are considered different if there exists such a cell that appears in one path and doesn't appear in the other path.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \le n, m \le 1000$$$; $$$1 \le q \le 10^4$$$) — the sizes of the matrix and the number of queries.

Each of the next $$$q$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x \le n$$$; $$$1 \le y \le m$$$) — the description of each query.

## Output Format
Print $$$q$$$ integers — the $$$i$$$-th value should be equal to the number of different staircases after $$$i$$$ queries. Two staircases are considered different if there exists such a cell that appears in one path and doesn't appear in the other path.

## Examples
```input
2 2 8
1 1
1 1
1 1
2 2
1 1
1 2
2 1
1 1
```
```output
5
10
5
2
5
3
1
0
```
-----
```input
3 4 10
1 4
1 2
2 3
1 2
2 3
3 2
1 3
3 4
1 3
3 1
```
```output
49
35
24
29
49
39
31
23
29
27
```
-----
```input
1000 1000 2
239 634
239 634
```
```output
1332632508
1333333000
```

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

Let's denote the concatenation of two strings $$$x$$$ and $$$y$$$ as $$$x+y$$$. For example, "()()" $$$+$$$ ")(" $$$=$$$ "()())(".

You are given $$$n$$$ bracket sequences $$$s_1, s_2, \dots, s_n$$$. You can rearrange them in any order (you can rearrange only the strings themselves, but not the characters in them).

Your task is to rearrange the strings in such a way that the string $$$s_1 + s_2 + \dots + s_n$$$ has as many non-empty prefixes that are RBS as possible.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 20$$$).

Then $$$n$$$ lines follow, the $$$i$$$-th of them contains $$$s_i$$$ — a bracket sequence (a string consisting of characters "(" and/or ")". All sequences $$$s_i$$$ are non-empty, their total length does not exceed $$$4 \cdot 10^5$$$.

## Output Format
Print one integer — the maximum number of non-empty prefixes that are RBS for the string $$$s_1 + s_2 + \dots + s_n$$$, if the strings $$$s_1, s_2, \dots, s_n$$$ can be rearranged arbitrarily.

## Examples
```input
2
(
)
```
```output
1
```
-----
```input
4
()()())
(
(
)
```
```output
4
```
-----
```input
1
(())
```
```output
1
```
-----
```input
1
)(()
```
```output
0
```

## Note
In the first example, you can concatenate the strings as follows: "(" $$$+$$$ ")" $$$=$$$ "()", the resulting string will have one prefix, that is an RBS: "()".

In the second example, you can concatenate the strings as follows: "(" $$$+$$$ ")" $$$+$$$ "()()())" $$$+$$$ "(" $$$=$$$ "()()()())(", the resulting string will have four prefixes that are RBS: "()", "()()", "()()()", "()()()()".

The third and the fourth examples contain only one string each, so the order is fixed.

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
Let's call a positive integer good if there is no digit 0 in its decimal representation.

For an array of a good numbers $$$a$$$, one found out that the sum of some two neighboring elements is equal to $$$x$$$ (i.e. $$$x = a_i + a_{i + 1}$$$ for some $$$i$$$). $$$x$$$ had turned out to be a good number as well.

Then the elements of the array $$$a$$$ were written out one after another without separators into one string $$$s$$$. For example, if $$$a = [12, 5, 6, 133]$$$, then $$$s = 1256133$$$.

You are given a string $$$s$$$ and a number $$$x$$$. Your task is to determine the positions in the string that correspond to the adjacent elements of the array that have sum $$$x$$$. If there are several possible answers, you can print any of them.

## Input Format
The first line contains the string $$$s$$$ ($$$2 \le |s| \le 5 \cdot 10^5$$$).

The second line contains an integer $$$x$$$ ($$$2 \le x < 10^{200000}$$$).

An additional constraint on the input: the answer always exists, i.e you can always select two adjacent substrings of the string $$$s$$$ so that if you convert these substrings to integers, their sum is equal to $$$x$$$.

## Output Format
In the first line, print two integers $$$l_1$$$, $$$r_1$$$, meaning that the first term of the sum ($$$a_i$$$) is in the string $$$s$$$ from position $$$l_1$$$ to position $$$r_1$$$.

In the second line, print two integers $$$l_2$$$, $$$r_2$$$, meaning that the second term of the sum ($$$a_{i + 1}$$$) is in the string $$$s$$$ from position $$$l_2$$$ to position $$$r_2$$$.

## Examples
```input
1256133
17
```
```output
1 2
3 3
```
-----
```input
9544715561
525
```
```output
2 3
4 6
```
-----
```input
239923
5
```
```output
1 1
2 2
```
-----
```input
1218633757639
976272
```
```output
2 7
8 13
```

## Note
In the first example $$$s[1;2] = 12$$$ and $$$s[3;3] = 5$$$, $$$12+5=17$$$.

In the second example $$$s[2;3] = 54$$$ and $$$s[4;6] = 471$$$, $$$54+471=525$$$.

In the third example $$$s[1;1] = 2$$$ and $$$s[2;2] = 3$$$, $$$2+3=5$$$.

In the fourth example $$$s[2;7] = 218633$$$ and $$$s[8;13] = 757639$$$, $$$218633+757639=976272$$$.

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've got another problem dealing with arrays. Let's consider an arbitrary sequence containing n (not necessarily different) integers a1, a2, ..., an. We are interested in all possible pairs of numbers (ai, aj), (1 ≤ i, j ≤ n). In other words, let's consider all n2 pairs of numbers, picked from the given array.

For example, in sequence a = {3, 1, 5} are 9 pairs of numbers: (3, 3), (3, 1), (3, 5), (1, 3), (1, 1), (1, 5), (5, 3), (5, 1), (5, 5).

Let's sort all resulting pairs lexicographically by non-decreasing. Let us remind you that pair (p1, q1) is lexicographically less than pair (p2, q2) only if either p1 < p2, or p1 = p2 and q1 < q2.

Then the sequence, mentioned above, will be sorted like that: (1, 1), (1, 3), (1, 5), (3, 1), (3, 3), (3, 5), (5, 1), (5, 3), (5, 5)

Let's number all the pair in the sorted list from 1 to n2. Your task is formulated like this: you should find the k-th pair in the ordered list of all possible pairs of the array you've been given.

## Input Format
The first line contains two integers n and k (1 ≤ n ≤ 105, 1 ≤ k ≤ n2). The second line contains the array containing n integers a1, a2, ..., an ( - 109 ≤ ai ≤ 109). The numbers in the array can coincide. All numbers are separated with spaces.

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout, streams or the %I64d specificator instead.

## Output Format
In the single line print two numbers — the sought k-th pair.

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

## Note
In the first sample the sorted sequence for the given array looks as: (1, 1), (1, 2), (2, 1), (2, 2). The 4-th of them is pair (2, 2).

The sorted sequence for the array from the second sample is given in the statement. The 2-nd pair there is (1, 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 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
You are given a connected weighted undirected graph without any loops and multiple edges.

Let us remind you that a graph's spanning tree is defined as an acyclic connected subgraph of the given graph that includes all of the graph's vertexes. The weight of a tree is defined as the sum of weights of the edges that the given tree contains. The minimum spanning tree (MST) of a graph is defined as the graph's spanning tree having the minimum possible weight. For any connected graph obviously exists the minimum spanning tree, but in the general case, a graph's minimum spanning tree is not unique.

Your task is to determine the following for each edge of the given graph: whether it is either included in any MST, or included at least in one MST, or not included in any MST.

## Input Format
The first line contains two integers n and m (2 ≤ n ≤ 105, $$n-1 \leq m \leq \min(10^5, \frac{n(n-1)}{2})$$) — the number of the graph's vertexes and edges, correspondingly. Then follow m lines, each of them contains three integers — the description of the graph's edges as "ai bi wi" (1 ≤ ai, bi ≤ n, 1 ≤ wi ≤ 106, ai ≠ bi), where ai and bi are the numbers of vertexes connected by the i-th edge, wi is the edge's weight. It is guaranteed that the graph is connected and doesn't contain loops or multiple edges.

## Output Format
Print m lines — the answers for all edges. If the i-th edge is included in any MST, print "any"; if the i-th edge is included at least in one MST, print "at least one"; if the i-th edge isn't included in any MST, print "none". Print the answers for the edges in the order in which the edges are specified in the input.

## Examples
```input
4 5
1 2 101
1 3 100
2 3 2
2 4 2
3 4 1
```
```output
none
any
at least one
at least one
any
```
-----
```input
3 3
1 2 1
2 3 1
1 3 2
```
```output
any
any
none
```
-----
```input
3 3
1 2 1
2 3 1
1 3 1
```
```output
at least one
at least one
at least one
```

## Note
In the second sample the MST is unique for the given graph: it contains two first edges.

In the third sample any two edges form the MST for the given graph. That means that each edge is included at least in one MST.

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
A number $$$a_2$$$ is said to be the arithmetic mean of two numbers $$$a_1$$$ and $$$a_3$$$, if the following condition holds: $$$a_1 + a_3 = 2\cdot a_2$$$.

We define an arithmetic mean deviation of three numbers $$$a_1$$$, $$$a_2$$$ and $$$a_3$$$ as follows: $$$d(a_1, a_2, a_3) = |a_1 + a_3 - 2 \cdot a_2|$$$.

Arithmetic means a lot to Jeevan. He has three numbers $$$a_1$$$, $$$a_2$$$ and $$$a_3$$$ and he wants to minimize the arithmetic mean deviation $$$d(a_1, a_2, a_3)$$$. To do so, he can perform the following operation any number of times (possibly zero):

- Choose $$$i, j$$$ from $$$\{1, 2, 3\}$$$ such that $$$i \ne j$$$ and increment $$$a_i$$$ by $$$1$$$ and decrement $$$a_j$$$ by $$$1$$$

Help Jeevan find out the minimum value of $$$d(a_1, a_2, a_3)$$$ that can be obtained after applying the operation any number of times.

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

The first and only line of each test case contains three integers $$$a_1$$$, $$$a_2$$$ and $$$a_3$$$ $$$(1 \le a_1, a_2, a_3 \le 10^{8})$$$.

## Output Format
For each test case, output the minimum value of $$$d(a_1, a_2, a_3)$$$ that can be obtained after applying the operation any number of times.

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

## Note
Note that after applying a few operations, the values of $$$a_1$$$, $$$a_2$$$ and $$$a_3$$$ may become negative.

In the first test case, $$$4$$$ is already the Arithmetic Mean of $$$3$$$ and $$$5$$$.

$$$d(3, 4, 5) = |3 + 5 - 2 \cdot 4| = 0$$$

In the second test case, we can apply the following operation:

$$$(2, 2, 6)$$$ $$$\xrightarrow[\text{increment $$$a_2$$$}]{\text{decrement $$$a_1$$$}}$$$ $$$(1, 3, 6)$$$

$$$d(1, 3, 6) = |1 + 6 - 2 \cdot 3| = 1$$$

It can be proven that answer can not be improved any further.

In the third test case, we can apply the following operations:

$$$(1, 6, 5)$$$ $$$\xrightarrow[\text{increment $$$a_3$$$}]{\text{decrement $$$a_2$$$}}$$$ $$$(1, 5, 6)$$$ $$$\xrightarrow[\text{increment $$$a_1$$$}]{\text{decrement $$$a_2$$$}}$$$ $$$(2, 4, 6)$$$

$$$d(2, 4, 6) = |2 + 6 - 2 \cdot 4| = 0$$$

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
Ashish has a string $$$s$$$ of length $$$n$$$ containing only characters 'a', 'b' and 'c'.

He wants to find the length of the smallest substring, which satisfies the following conditions:

- Length of the substring is at least $$$2$$$
- 'a' occurs strictly more times in this substring than 'b'
- 'a' occurs strictly more times in this substring than 'c'

Ashish is busy planning his next Codeforces round. Help him solve the problem.

A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

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

The first line of each test case contains a single integer $$$n$$$ $$$(2 \le n \le 10^{6})$$$  — the length of the string $$$s$$$.

The second line of each test case contains a string $$$s$$$ consisting only of characters 'a', 'b' and 'c'.

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

## Output Format
For each test case, output the length of the smallest substring which satisfies the given conditions or print $$$-1$$$ if there is no such substring.

## Examples
```input
3
2
aa
5
cbabb
8
cacabccc
```
```output
2
-1
3
```

## Note
Consider the first test case. In the substring "aa", 'a' occurs twice, while 'b' and 'c' occur zero times. Since 'a' occurs strictly more times than 'b' and 'c', the substring "aa" satisfies the condition and the answer is $$$2$$$. The substring "a" also satisfies this condition, however its length is not at least $$$2$$$.

In the second test case, it can be shown that in none of the substrings of "cbabb" does 'a' occur strictly more times than 'b' and 'c' each.

In the third test case, "cacabccc", the length of the smallest substring that satisfies the conditions is $$$3$$$.

Now solve the problem and return the code.