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
The knight is standing in front of a long and narrow hallway. A princess is waiting at the end of it.

In a hallway there are three doors: a red door, a green door and a blue door. The doors are placed one after another, however, possibly in a different order. To proceed to the next door, the knight must first open the door before.

Each door can be only opened with a key of the corresponding color. So three keys: a red key, a green key and a blue key — are also placed somewhere in the hallway. To open the door, the knight should first pick up the key of its color.

The knight has a map of the hallway. It can be transcribed as a string, consisting of six characters:

- R, G, B — denoting red, green and blue doors, respectively;
- r, g, b — denoting red, green and blue keys, respectively.

Each of these six characters appears in the string exactly once.

The knight is standing at the beginning of the hallway — on the left on the map.

Given a map of the hallway, determine if the knight can open all doors and meet the princess at the end of the hallway.

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

Each testcase consists of a single string. Each character is one of R, G, B (for the doors), r, g, b (for the keys), and each of them appears exactly once.

## Output Format
For each testcase, print YES if the knight can open all doors. Otherwise, print NO.

## Examples
```input
4
rgbBRG
RgbrBG
bBrRgG
rgRGBb
```
```output
YES
NO
YES
NO
```

## Note
In the first testcase, the knight first collects all keys, then opens all doors with them.

In the second testcase, there is a red door right in front of the knight, but he doesn't have a key for it.

In the third testcase, the key to each door is in front of each respective door, so the knight collects the key and uses it immediately three times.

In the fourth testcase, the knight can't open the blue door.

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
There is a sheet of paper that can be represented with a grid of size $$$n \times m$$$: $$$n$$$ rows and $$$m$$$ columns of cells. All cells are colored in white initially.

$$$q$$$ operations have been applied to the sheet. The $$$i$$$-th of them can be described as follows:

- $$$x_i$$$ $$$y_i$$$ — choose one of $$$k$$$ non-white colors and color the entire row $$$x_i$$$ and the entire column $$$y_i$$$ in it. The new color is applied to each cell, regardless of whether the cell was colored before the operation.

The sheet after applying all $$$q$$$ operations is called a coloring. Two colorings are different if there exists at least one cell that is colored in different colors.

How many different colorings are there? Print the number modulo $$$998\,244\,353$$$.

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

The first line of the testcase contains four integers $$$n, m, k$$$ and $$$q$$$ ($$$1 \le n, m, k, q \le 2 \cdot 10^5$$$) — the size of the sheet, the number of non-white colors and the number of operations.

The $$$i$$$-th of the following $$$q$$$ lines contains a description of the $$$i$$$-th operation — two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i \le n$$$; $$$1 \le y_i \le m$$$) — the row and the column the operation is applied to.

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

## Output Format
For each testcase, print a single integer — the number of different colorings modulo $$$998\,244\,353$$$.

## Examples
```input
2
1 1 3 2
1 1
1 1
2 2 2 3
2 1
1 1
2 2
```
```output
3
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 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've got another geometrical task. You are given two non-degenerate polygons A and B as vertex coordinates. Polygon A is strictly convex. Polygon B is an arbitrary polygon without any self-intersections and self-touches. The vertices of both polygons are given in the clockwise order. For each polygon no three consecutively following vertices are located on the same straight line.

Your task is to check whether polygon B is positioned strictly inside polygon A. It means that any point of polygon B should be strictly inside polygon A. "Strictly" means that the vertex of polygon B cannot lie on the side of the polygon A.

## Input Format
The first line contains the only integer n (3 ≤ n ≤ 105) — the number of vertices of polygon A. Then n lines contain pairs of integers xi, yi (|xi|, |yi| ≤ 109) — coordinates of the i-th vertex of polygon A. The vertices are given in the clockwise order.

The next line contains a single integer m (3 ≤ m ≤ 2·104) — the number of vertices of polygon B. Then following m lines contain pairs of integers xj, yj (|xj|, |yj| ≤ 109) — the coordinates of the j-th vertex of polygon B. The vertices are given in the clockwise order.

The coordinates of the polygon's vertices are separated by a single space. It is guaranteed that polygons A and B are non-degenerate, that polygon A is strictly convex, that polygon B has no self-intersections and self-touches and also for each polygon no three consecutively following vertices are located on the same straight line.

## Output Format
Print on the only line the answer to the problem — if polygon B is strictly inside polygon A, print "YES", otherwise print "NO" (without the quotes).

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

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

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
A median in an array with the length of n is an element which occupies position number $$\left\lfloor \frac{n+1}{2} \right\rfloor$$ after we sort the elements in the non-decreasing order (the array elements are numbered starting with 1). A median of an array (2, 6, 1, 2, 3) is the number 2, and a median of array (0, 96, 17, 23) — the number 17.

We define an expression $$\left[\frac{a}{b}\right]$$ as the integer part of dividing number a by number b.

One day Vasya showed Petya an array consisting of n integers and suggested finding the array's median. Petya didn't even look at the array and said that it equals x. Petya is a very honest boy, so he decided to add several numbers to the given array so that the median of the resulting array would be equal to x.

Petya can add any integers from 1 to 105 to the array, including the same numbers. Of course, he can add nothing to the array. If a number is added multiple times, then we should consider it the number of times it occurs. It is not allowed to delete of change initial numbers of the array.

While Petya is busy distracting Vasya, your task is to find the minimum number of elements he will need.

## Input Format
The first input line contains two space-separated integers n and x (1 ≤ n ≤ 500, 1 ≤ x ≤ 105) — the initial array's length and the required median's value. The second line contains n space-separated numbers — the initial array. The elements of the array are integers from 1 to 105. The array elements are not necessarily different.

## Output Format
Print the only integer — the minimum number of elements Petya needs to add to the array so that its median equals x.

## Examples
```input
3 10
10 20 30
```
```output
1
```
-----
```input
3 4
1 2 3
```
```output
4
```

## Note
In the first sample we can add number 9 to array (10, 20, 30). The resulting array (9, 10, 20, 30) will have a median in position $$\left\lfloor \frac{4+1}{2} \right\rfloor = 2$$, that is, 10.

In the second sample you should add numbers 4, 5, 5, 5. The resulting array has median equal to 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 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
The warehouse in your shop has n shoe pairs. Each pair is characterized by two integers: its price ci and its size si. We know that on this very day all numbers si are different, that is, there is no more than one pair of each size.

The shop has m customers who came at the same time. The customer number i has di money and the size of his feet equals li. The customer number i can buy the pair number j, if cj ≤ di, and also if li = sj or li = sj - 1; that is, it is necessary that he has enough money to pay for the shoes. It is also necessary that the size of his feet equals to or is less by 1 than the size of the shoes he chooses.

Your task is to sell some customers pairs of shoes (a pair per person) so as to maximize the sum of the sold pairs cj that is, the profit. It is guaranteed that each customer buys no more than one pair and each pair will be bought by no more than one customer.

## Input Format
The first input line contains the only integer n (1 ≤ n ≤ 105) — the number of shoe pairs in the warehouse. Then n lines contain the descriptions of pairs of shoes as two integers ci and si (1 ≤ ci, si ≤ 109), the numbers are separated by a space. It is guaranteed that all numbers si are different.

The next line contains an integer m (1 ≤ m ≤ 105) — the number of customers in the shop. Next m lines contain the customers' descriptions as two integers di and li (1 ≤ di, li ≤ 109), the numbers are separated by a space.

## Output Format
In the first line print the only integer — the maximum profit you can get from selling shoes. In the second line print an integer k — the number of shoe pairs you will sell. In the following k lines print the descriptions of the sold pairs — two space-separated integers where the first number is the customer's number and the second number is the number of the shoes the customer will buy.

You can print pairs of numbers "the customer's number and the shoes' number" in any order, the customers and the pairs of shoes are numbered starting from 1 in the order in which they are given in the input. If there are several optimal answers, you are allowed to print any of them.

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

## Examples
```input
3
10 1
30 2
20 3
2
20 1
20 2
```
```output
30
2
2 3
1 1
```
-----
```input
3
10 4
20 5
30 6
2
70 4
50 5
```
```output
50
2
2 3
1 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 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 tetrahedron. Let's mark its vertices with letters A, B, C and D correspondingly.

An ant is standing in the vertex D of the tetrahedron. The ant is quite active and he wouldn't stay idle. At each moment of time he makes a step from one vertex to another one along some edge of the tetrahedron. The ant just can't stand on one place.

You do not have to do much to solve the problem: your task is to count the number of ways in which the ant can go from the initial vertex D to itself in exactly n steps. In other words, you are asked to find out the number of different cyclic paths with the length of n from vertex D to itself. As the number can be quite large, you should print it modulo 1000000007 (109 + 7).

## Input Format
The first line contains the only integer n (1 ≤ n ≤ 107) — the required length of the cyclic path.

## Output Format
Print the only integer — the required number of ways modulo 1000000007 (109 + 7).

## Examples
```input
2
```
```output
3
```
-----
```input
4
```
```output
21
```

## Note
The required paths in the first sample are:

- D - A - D
- D - B - D
- D - C - D

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
Codeforces separates its users into $$$4$$$ divisions by their rating:

- For Division 1: $$$1900 \leq \mathrm{rating}$$$
- For Division 2: $$$1600 \leq \mathrm{rating} \leq 1899$$$
- For Division 3: $$$1400 \leq \mathrm{rating} \leq 1599$$$
- For Division 4: $$$\mathrm{rating} \leq 1399$$$

Given a $$$\mathrm{rating}$$$, print in which division the $$$\mathrm{rating}$$$ belongs.

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

The description of each test consists of one line containing one integer $$$\mathrm{rating}$$$ ($$$-5000 \leq \mathrm{rating} \leq 5000$$$).

## Output Format
For each test case, output a single line containing the correct division in the format "Division X", where $$$X$$$ is an integer between $$$1$$$ and $$$4$$$ representing the division for the corresponding rating.

## Examples
```input
7
-789
1299
1300
1399
1400
1679
2300
```
```output
Division 4
Division 4
Division 4
Division 4
Division 3
Division 2
Division 1
```

## Note
For test cases $$$1-4$$$, the corresponding ratings are $$$-789$$$, $$$1299$$$, $$$1300$$$, $$$1399$$$, so all of them are in division $$$4$$$.

For the fifth test case, the corresponding rating is $$$1400$$$, so it is in division $$$3$$$.

For the sixth test case, the corresponding rating is $$$1679$$$, so it is in division $$$2$$$.

For the seventh test case, the corresponding rating is $$$2300$$$, so it is in division $$$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 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
Given an array $$$a$$$ of $$$n$$$ elements, print any value that appears at least three times or print -1 if there is no such value.

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — the elements of the array.

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

## Output Format
For each test case, print any value that appears at least three times or print -1 if there is no such value.

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

## Note
In the first test case there is just a single element, so it can't occur at least three times and the answer is -1.

In the second test case, all three elements of the array are equal to $$$2$$$, so $$$2$$$ occurs three times, and so the answer is $$$2$$$.

For the third test case, $$$2$$$ occurs four times, so the answer is $$$2$$$.

For the fourth test case, $$$4$$$ occurs three times, so the answer is $$$4$$$.

For the fifth test case, $$$1$$$, $$$2$$$ and $$$3$$$ all occur at least three times, so they are all valid outputs.

For the sixth test case, all elements are distinct, so none of them occurs at least three times and the answer is -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 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
Given an array $$$a=[a_1,a_2,\dots,a_n]$$$ of $$$n$$$ positive integers, you can do operations of two types on it:

1. Add $$$1$$$ to every element with an odd index. In other words change the array as follows: $$$a_1 := a_1 +1, a_3 := a_3 + 1, a_5 := a_5+1, \dots$$$.
2. Add $$$1$$$ to every element with an even index. In other words change the array as follows: $$$a_2 := a_2 +1, a_4 := a_4 + 1, a_6 := a_6+1, \dots$$$.

Determine if after any number of operations it is possible to make the final array contain only even numbers or only odd numbers. In other words, determine if you can make all elements of the array have the same parity after any number of operations.

Note that you can do operations of both types any number of times (even none). Operations of different types can be performed a different number of times.

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

The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 50$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^3$$$) — the elements of the array.

Note that after the performed operations the elements in the array can become greater than $$$10^3$$$.

## Output Format
Output $$$t$$$ lines, each of which contains the answer to the corresponding test case. As an answer, output "YES" if after any number of operations it is possible to make the final array contain only even numbers or only odd numbers, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

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

## Note
For the first test case, we can increment the elements with an even index, obtaining the array $$$[1, 3, 1]$$$, which contains only odd numbers, so the answer is "YES".

For the second test case, we can show that after performing any number of operations we won't be able to make all elements have the same parity, so the answer is "NO".

For the third test case, all elements already have the same parity so the answer is "YES".

For the fourth test case, we can perform one operation and increase all elements at odd positions by $$$1$$$, thus obtaining the array $$$[1001, 1, 1001, 1, 1001]$$$, and all elements become odd so the answer is "YES".

Now solve the problem and return the code.