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
Once upon a time, Petya had an array of integers $$$a$$$ of length $$$n$$$. But over time, the array itself was lost, and only $$$n-1$$$ results of comparisons of neighboring array elements remained. In other words, for every $$$i$$$ from $$$1$$$ to $$$n-1$$$, Petya knows exactly one of these three facts:

- $$$a_i < a_{i+1}$$$;
- $$$a_i = a_{i+1}$$$;
- $$$a_i > a_{i+1}$$$.

Petya wonders if it is possible to uniquely determine the result of comparing $$$a_1$$$ and $$$a_n$$$.

You have to help Petya determine the result of comparing $$$a_1$$$ and $$$a_n$$$ or report that the result cannot be determined unambiguously.

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

The only line of the test case contains the string $$$s$$$ ($$$1 \le |s| \le 100$$$), where $$$s_i$$$ is:

- <, if $$$a_i < a_{i + 1}$$$;
- >, if $$$a_i > a_{i + 1}$$$;
- =, if $$$a_i = a_{i + 1}$$$.

## Output Format
For each test case, print a single string equal to:

- <, if $$$a_1 < a_n$$$;
- >, if $$$a_1 > a_n$$$;
- =, if $$$a_1 = a_n$$$;
- ?, if it is impossible to uniquely determine the result of the comparison.

## Examples
```input
4
>>>
<><=<
=
<<==
```
```output
>
?
=
<
```

## Note
Consider the test cases of the example:

- in the first test case, it's easy to see that $$$a_1 > a_4$$$ since $$$a_1 > a_2 > a_3 > a_4$$$;
- in the second test case, both sequences $$$[1, 2, 0, 10, 10, 15]$$$ and $$$[10, 11, 1, 2, 2, 5]$$$ meet the constraints; in the first one, $$$a_1 < a_6$$$, and in the second one, $$$a_1 > a_6$$$, so it's impossible to compare $$$a_1$$$ and $$$a_6$$$;
- in the third test case, we already know that $$$a_1 = a_2$$$;
- in the fourth test case, it's easy to see that $$$a_3 = a_4 = a_5$$$, and $$$a_1 < a_2 < a_3$$$, so $$$a_1 < a_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
Let's say that two strings $$$s$$$ and $$$t$$$ rhyme if both strings have length at least $$$k$$$, and their last $$$k$$$ characters are equal. For example, if $$$k = 3$$$, the strings abcd and cebcd rhyme, the strings ab and ab don't rhyme, the strings aaaa and aaaaa rhyme, the strings abcd and abce don't rhyme.

You have $$$n$$$ pairs of strings $$$(s_i, t_i)$$$, and for each pair of strings you know, should they rhyme or should not.

Find all possible non-negative integer values for $$$k$$$ such that pairs that have to rhyme, rhyme and pairs that must not rhyme, don't rhyme.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of string pairs.

Next $$$n$$$ lines contains descriptions of pairs — one per line. The $$$i$$$-th line contains space-separated strings $$$s_i$$$ and $$$t_i$$$ and marker $$$r_i$$$. Strings are non-empty, consist of lowercase Latin letters and each have length at most $$$2 \cdot 10^5$$$. The marker $$$r_i$$$ equals to $$$1$$$ if strings have to rhyme, or $$$0$$$ if they must not rhyme.

It's guaranteed that for each test case there is at least one pair with $$$r_i$$$ equal to $$$1$$$ and that the total length of all strings over all test cases doesn't exceed $$$4 \cdot 10^5$$$.

## Output Format
For each test case, firstly print integer $$$m$$$ — the number of possible non-negative integer values of $$$k$$$ such that pairs that have to rhyme, rhyme and pairs that must not rhyme, don't rhyme. Next, print all these values of $$$k$$$ (without repetitions). You can print them in any order.

## Examples
```input
3
1
kotlin heroes 1
2
join kotlin 1
episode eight 0
4
abc abcdef 0
xyz zzz 1
aaa bba 0
c d 0
```
```output
1
0
2
1 2
0
```

## Note
In the first test case, if $$$k$$$ is at least $$$1$$$ then kotlin and heroes don't rhyme.

In the second test case, for $$$k = 2$$$ join and kotlin rhyme, and episode and eight don't rhyme.

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

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

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

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
Kotlinforces is a web platfrom that hosts programming competitions.

The staff of Kotlinforces is asked to schedule $$$n$$$ programming competitions on the next $$$m$$$ days. Each competition is held in multiple stages; the regulations of the $$$i$$$-th competition state that this competition should consist of exactly $$$k_i$$$ stages, and each stage, starting from the second one, should be scheduled exactly $$$t_i$$$ days after the previous stage. In other words, if the first stage of the $$$i$$$-th competition is scheduled on day $$$x$$$, the second stage should be scheduled on day $$$x+t_i$$$, the third stage — on day $$$x+2t_i$$$, ..., the $$$k_i$$$-th stage (which is the last one) — on day $$$x+(k_i-1)t_i$$$.

All $$$n$$$ competitions should be scheduled in such a way that they start and finish during the next $$$m$$$ days, and on any of these $$$m$$$ days, at most one stage of one competition is held (two stages of different competitions should not be scheduled on the same day).

Is it possible to schedule all $$$n$$$ competitions to meet these constraints?

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 5000$$$) — the number of competitions and the number of days, respectively.

Then $$$n$$$ lines follow, each describing a competition which should be scheduled. The $$$i$$$-th line contains two integers $$$k_i$$$ and $$$t_i$$$ ($$$2 \le k_i \le 5000$$$; $$$1 \le t_i \le 2$$$) — the parameters of the $$$i$$$-th competition.

## Output Format
If it is impossible to schedule all $$$n$$$ competitions on the next $$$m$$$ days so that there is at most one stage during each day, print -1.

Otherwise, print $$$n$$$ integers. The $$$i$$$-th integer should represent the day when the first stage of the $$$i$$$-th competition is scheduled; days are numbered from $$$1$$$ to $$$m$$$. If there are multiple answers, print any of them.

## Examples
```input
3 7
3 2
2 2
2 2
```
```output
2 5 1
```
-----
```input
1 7
4 2
```
```output
1
```
-----
```input
1 7
5 2
```
```output
-1
```
-----
```input
2 4
2 1
2 2
```
```output
-1
```
-----
```input
2 5
2 1
2 2
```
```output
4 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Casimir has a string $$$s$$$ which consists of capital Latin letters 'A', 'B', and 'C' only. Each turn he can choose to do one of the two following actions:

- he can either erase exactly one letter 'A' and exactly one letter 'B' from arbitrary places of the string (these letters don't have to be adjacent);
- or he can erase exactly one letter 'B' and exactly one letter 'C' from arbitrary places in the string (these letters don't have to be adjacent).

Therefore, each turn the length of the string is decreased exactly by $$$2$$$. All turns are independent so for each turn, Casimir can choose any of two possible actions.

For example, with $$$s$$$ $$$=$$$ "ABCABC" he can obtain a string $$$s$$$ $$$=$$$ "ACBC" in one turn (by erasing the first occurrence of 'B' and the second occurrence of 'A'). There are also many other options for a turn aside from this particular example.

For a given string $$$s$$$ determine whether there is a sequence of actions leading to an empty string. In other words, Casimir's goal is to erase all letters from the string. Is there a way to do this?

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

Each test case is described by one string $$$s$$$, for which you need to determine if it can be fully erased by some sequence of turns. The string $$$s$$$ consists of capital letters 'A', 'B', 'C' and has a length from $$$1$$$ to $$$50$$$ letters, inclusive.

## Output Format
Print $$$t$$$ lines, each line containing the answer to the corresponding test case. The answer to a test case should be YES if there is a way to fully erase the corresponding string and NO otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes, and YES will all be recognized as positive answers).

## Examples
```input
6
ABACAB
ABBA
AC
ABC
CABCBB
BCBCBCBCBCBCBCBC
```
```output
NO
YES
NO
NO
YES
YES
```

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
An important meeting is to be held and there are exactly $$$n$$$ people invited. At any moment, any two people can step back and talk in private. The same two people can talk several (as many as they want) times per meeting.

Each person has limited sociability. The sociability of the $$$i$$$-th person is a non-negative integer $$$a_i$$$. This means that after exactly $$$a_i$$$ talks this person leaves the meeting (and does not talk to anyone else anymore). If $$$a_i = 0$$$, the $$$i$$$-th person leaves the meeting immediately after it starts.

A meeting is considered most productive if the maximum possible number of talks took place during it.

You are given an array of sociability $$$a$$$, determine which people should talk to each other so that the total number of talks is as large as possible.

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

The next $$$2t$$$ lines contain descriptions of the test cases.

The first line of each test case description contains an integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) —the number of people in the meeting. The second line consists of $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2 \cdot 10^5$$$) — the sociability parameters of all people.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$. It is also guaranteed that the sum of all $$$a_i$$$ (over all test cases and all $$$i$$$) does not exceed $$$2 \cdot 10^5$$$.

## Output Format
Print $$$t$$$ answers to all test cases.

On the first line of each answer print the number $$$k$$$ — the maximum number of talks possible in a meeting.

On each of the next $$$k$$$ lines print two integers $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$ and $$$i \neq j$$$) — the numbers of people who will have another talk.

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

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

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

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Theofanis has a riddle for you and if you manage to solve it, he will give you a Cypriot snack halloumi for free (Cypriot cheese).

You are given an integer $$$n$$$. You need to find two integers $$$l$$$ and $$$r$$$ such that $$$-10^{18} \le l < r \le 10^{18}$$$ and $$$l + (l + 1) + \ldots + (r - 1) + r = n$$$.

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

The first and only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^{18}$$$).

## Output Format
For each test case, print the two integers $$$l$$$ and $$$r$$$ such that $$$-10^{18} \le l < r \le 10^{18}$$$ and $$$l + (l + 1) + \ldots + (r - 1) + r = n$$$.

It can be proven that an answer always exists. If there are multiple answers, print any.

## Examples
```input
7
1
2
3
6
100
25
3000000000000
```
```output
0 1
-1 2 
1 2 
1 3 
18 22
-2 7
999999999999 1000000000001
```

## Note
In the first test case, $$$0 + 1 = 1$$$.

In the second test case, $$$(-1) + 0 + 1 + 2 = 2$$$.

In the fourth test case, $$$1 + 2 + 3 = 6$$$.

In the fifth test case, $$$18 + 19 + 20 + 21 + 22 = 100$$$.

In the sixth test case, $$$(-2) + (-1) + 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 = 25$$$.

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
Theofanis really likes sequences of positive integers, thus his teacher (Yeltsa Kcir) gave him a problem about a sequence that consists of only special numbers.

Let's call a positive number special if it can be written as a sum of different non-negative powers of $$$n$$$. For example, for $$$n = 4$$$ number $$$17$$$ is special, because it can be written as $$$4^0 + 4^2 = 1 + 16 = 17$$$, but $$$9$$$ is not.

Theofanis asks you to help him find the $$$k$$$-th special number if they are sorted in increasing order. Since this number may be too large, output it modulo $$$10^9+7$$$.

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

The first and only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^9$$$; $$$1 \le k \le 10^9$$$).

## Output Format
For each test case, print one integer — the $$$k$$$-th special number in increasing order modulo $$$10^9+7$$$.

## Examples
```input
3
3 4
2 12
105 564
```
```output
9
12
3595374
```

## Note
For $$$n = 3$$$ the sequence is $$$[1,3,4,9...]$$$

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
It is the easy version of the problem. The difference is that in this version, there are no nodes with already chosen colors.

Theofanis is starving, and he wants to eat his favorite food, sheftalia. However, he should first finish his homework. Can you help him with this problem?

You have a perfect binary tree of $$$2^k - 1$$$ nodes — a binary tree where all vertices $$$i$$$ from $$$1$$$ to $$$2^{k - 1} - 1$$$ have exactly two children: vertices $$$2i$$$ and $$$2i + 1$$$. Vertices from $$$2^{k - 1}$$$ to $$$2^k - 1$$$ don't have any children. You want to color its vertices with the $$$6$$$ Rubik's cube colors (White, Green, Red, Blue, Orange and Yellow).

Let's call a coloring good when all edges connect nodes with colors that are neighboring sides in the Rubik's cube.

A picture of Rubik's cube and its 2D map.

More formally:

- a white node can not be neighboring with white and yellow nodes;
- a yellow node can not be neighboring with white and yellow nodes;
- a green node can not be neighboring with green and blue nodes;
- a blue node can not be neighboring with green and blue nodes;
- a red node can not be neighboring with red and orange nodes;
- an orange node can not be neighboring with red and orange nodes;

You want to calculate the number of the good colorings of the binary tree. Two colorings are considered different if at least one node is colored with a different color.

The answer may be too large, so output the answer modulo $$$10^9+7$$$.

## Input Format
The first and only line contains the integers $$$k$$$ ($$$1 \le k \le 60$$$) — the number of levels in the perfect binary tree you need to color.

## Output Format
Print one integer — the number of the different colorings modulo $$$10^9+7$$$.

## Examples
```input
3
```
```output
24576
```
-----
```input
14
```
```output
934234
```

## Note
In the picture below, you can see one of the correct colorings of the first example.

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
It is the hard version of the problem. The difference is that in this version, there are nodes with already chosen colors.

Theofanis is starving, and he wants to eat his favorite food, sheftalia. However, he should first finish his homework. Can you help him with this problem?

You have a perfect binary tree of $$$2^k - 1$$$ nodes — a binary tree where all vertices $$$i$$$ from $$$1$$$ to $$$2^{k - 1} - 1$$$ have exactly two children: vertices $$$2i$$$ and $$$2i + 1$$$. Vertices from $$$2^{k - 1}$$$ to $$$2^k - 1$$$ don't have any children. You want to color its vertices with the $$$6$$$ Rubik's cube colors (White, Green, Red, Blue, Orange and Yellow).

Let's call a coloring good when all edges connect nodes with colors that are neighboring sides in the Rubik's cube.

A picture of Rubik's cube and its 2D map.

More formally:

- a white node can not be neighboring with white and yellow nodes;
- a yellow node can not be neighboring with white and yellow nodes;
- a green node can not be neighboring with green and blue nodes;
- a blue node can not be neighboring with green and blue nodes;
- a red node can not be neighboring with red and orange nodes;
- an orange node can not be neighboring with red and orange nodes;

However, there are $$$n$$$ special nodes in the tree, colors of which are already chosen.

You want to calculate the number of the good colorings of the binary tree. Two colorings are considered different if at least one node is colored with a different color.

The answer may be too large, so output the answer modulo $$$10^9+7$$$.

## Input Format
The first line contains the integers $$$k$$$ ($$$1 \le k \le 60$$$) — the number of levels in the perfect binary tree you need to color.

The second line contains the integer $$$n$$$ ($$$1 \le n \le \min(2^k - 1, 2000)$$$) — the number of nodes, colors of which are already chosen.

The next $$$n$$$ lines contains integer $$$v$$$ ($$$1 \le v \le 2^k - 1$$$) and string $$$s$$$ — the index of the node and the color of the node ($$$s$$$ is one of the white, yellow, green, blue, red and orange).

It is guaranteed that each node $$$v$$$ appears in the input at most once.

## Output Format
Print one integer — the number of the different colorings modulo $$$10^9+7$$$.

## Examples
```input
3
2
5 orange
2 white
```
```output
1024
```
-----
```input
2
2
1 white
2 white
```
```output
0
```
-----
```input
10
3
1 blue
4 red
5 orange
```
```output
328925088
```

## Note
In the picture below, you can see one of the correct colorings of the first test example.

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
Theofanis decided to visit his uncle's farm. There are $$$s$$$ animals and $$$n$$$ animal pens on the farm. For utility purpose, animal pens are constructed in one row.

Uncle told Theofanis that a farm is lucky if you can distribute all animals in all pens in such a way that there are no empty pens and there is at least one continuous segment of pens that has exactly $$$k$$$ animals in total.

Moreover, a farm is ideal if it's lucky for any distribution without empty pens.

Neither Theofanis nor his uncle knows if their farm is ideal or not. Can you help them to figure it out?

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

The first and only line of each test case contains three integers $$$s$$$, $$$n$$$, and $$$k$$$ ($$$1 \le s, n, k \le 10^{18}$$$; $$$n \le s$$$).

## Output Format
For each test case, print YES (case-insensitive), if the farm is ideal, or NO (case-insensitive) otherwise.

## Examples
```input
4
1 1 1
1 1 2
100 50 200
56220 47258 14497
```
```output
YES
NO
NO
YES
```

## Note
For the first and the second test case, the only possible combination is $$$[1]$$$ so there always will be a subsegment with $$$1$$$ animal but not with $$$2$$$ animals.

Now solve the problem and return the code.