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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
$$$n$$$ players are playing a game.

There are two different maps in the game. For each player, we know his strength on each map. When two players fight on a specific map, the player with higher strength on that map always wins. No two players have the same strength on the same map.

You are the game master and want to organize a tournament. There will be a total of $$$n-1$$$ battles. While there is more than one player in the tournament, choose any map and any two remaining players to fight on it. The player who loses will be eliminated from the tournament.

In the end, exactly one player will remain, and he is declared the winner of the tournament. For each player determine if he can win the tournament.

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$, $$$a_i \neq a_j$$$ for $$$i \neq j$$$), where $$$a_i$$$ is the strength of the $$$i$$$-th player on the first map.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \leq b_i \leq 10^9$$$, $$$b_i \neq b_j$$$ for $$$i \neq j$$$), where $$$b_i$$$ is the strength of the $$$i$$$-th player on the second map.

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

## Output Format
For each test case print a string of length $$$n$$$. $$$i$$$-th character should be "1" if the $$$i$$$-th player can win the tournament, or "0" otherwise.

## Examples
```input
3
4
1 2 3 4
1 2 3 4
4
11 12 20 21
44 22 11 30
1
1000000000
1000000000
```
```output
0001
1111
1
```

## Note
In the first test case, the $$$4$$$-th player will beat any other player on any game, so he will definitely win the tournament.

In the second test case, everyone can be a winner.

In the third test case, there is only one player. Clearly, he will win the tournament.

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 are given $$$n$$$ dominoes. Each domino has a left and a right cell. Each cell can be colored either black or white. Some cells are already colored, while some aren't yet.

The coloring is said to be valid if and only if it is possible to rearrange the dominoes in some order such that for each $$$1 \le i \le n$$$ the color of the right cell of the $$$i$$$-th domino is different from the color of the left cell of the $$$((i \bmod n)+1)$$$-st domino.

Note that you can't rotate the dominoes, so the left cell always remains the left cell, and the right cell always remains the right cell.

Count the number of valid ways to color the yet uncolored cells of dominoes. Two ways are considered different if there is a cell that is colored white in one way and black in the other. In particular, colorings BW WB and WB BW different (and both invalid).

As this number can be very big, output it modulo $$$998\,244\,353$$$.

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

The next $$$n$$$ lines describe dominoes. Each line contains two characters which represent the left and the right cell. Character B means that the corresponding cell is black, character W means that the corresponding cell is white, and ? means that the cell is yet to be colored.

## Output Format
Print a single integer — the answer to the problem.

## Examples
```input
1
?W
```
```output
1
```
-----
```input
2
??
W?
```
```output
2
```
-----
```input
4
BB
??
W?
??
```
```output
10
```

## Note
In the first test case, there is only one domino, and we need the color of its right cell to be different from the color of its left cell. There is only one way to achieve this.

In the second test case, there are only $$$2$$$ such colorings:

BB WW and WB WB.

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
On an endless checkered sheet of paper, $$$n$$$ cells are chosen and colored in three colors, where $$$n$$$ is divisible by $$$3$$$. It turns out that there are exactly $$$\frac{n}{3}$$$ marked cells of each of three colors!

Find the largest such $$$k$$$ that it's possible to choose $$$\frac{k}{3}$$$ cells of each color, remove all other marked cells, and then select three rectangles with sides parallel to the grid lines so that the following conditions hold:

- No two rectangles can intersect (but they can share a part of the boundary). In other words, the area of intersection of any two of these rectangles must be $$$0$$$.
- The $$$i$$$-th rectangle contains all the chosen cells of the $$$i$$$-th color and no chosen cells of other colors, for $$$i = 1, 2, 3$$$.

## Input Format
The first line of the input contains a single integer $$$n$$$ — the number of the marked cells ($$$3 \leq n \le 10^5$$$, $$$n$$$ is divisible by 3).

The $$$i$$$-th of the following $$$n$$$ lines contains three integers $$$x_i$$$, $$$y_i$$$, $$$c_i$$$ ($$$|x_i|,|y_i| \leq 10^9$$$; $$$1 \leq c_i \leq 3$$$), where $$$(x_i, y_i)$$$ are the coordinates of the $$$i$$$-th marked cell and $$$c_i$$$ is its color.

It's guaranteed that all cells $$$(x_i, y_i)$$$ in the input are distinct, and that there are exactly $$$\frac{n}{3}$$$ cells of each color.

## Output Format
Output a single integer $$$k$$$ — the largest number of cells you can leave.

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

## Note
In the first sample, it's possible to leave $$$6$$$ cells with indexes $$$1, 5, 6, 7, 8, 9$$$.

In the second sample, it's possible to leave $$$3$$$ cells with indexes $$$1, 2, 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: 4.0 seconds
Memory limit: 256.0 MB

# Problem
For an array $$$c$$$ of nonnegative integers, $$$MEX(c)$$$ denotes the smallest nonnegative integer that doesn't appear in it. For example, $$$MEX([0, 1, 3]) = 2$$$, $$$MEX([42]) = 0$$$.

You are given integers $$$n, k$$$, and an array $$$[b_1, b_2, \ldots, b_n]$$$.

Find the number of arrays $$$[a_1, a_2, \ldots, a_n]$$$, for which the following conditions hold:

- $$$0 \le a_i \le n$$$ for each $$$i$$$ for each $$$i$$$ from $$$1$$$ to $$$n$$$.
- $$$|MEX([a_1, a_2, \ldots, a_i]) - b_i| \le k$$$ for each $$$i$$$ from $$$1$$$ to $$$n$$$.

As this number can be very big, output it modulo $$$998\,244\,353$$$.

## Input Format
The first line of the input contains two integers $$$n, k$$$ ($$$1 \le n \le 2000$$$, $$$0 \le k \le 50$$$).

The second line of the input contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$-k \le b_i \le n+k$$$) — elements of the array $$$b$$$.

## Output Format
Output a single integer — the number of arrays which satisfy the conditions from the statement, modulo $$$998\,244\,353$$$.

## Examples
```input
4 0
0 0 0 0
```
```output
256
```
-----
```input
4 1
0 0 0 0
```
```output
431
```
-----
```input
4 1
0 0 1 1
```
```output
509
```
-----
```input
5 2
0 0 2 2 0
```
```output
6546
```
-----
```input
3 2
-2 0 4
```
```output
11
```

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: 256.0 MB

# Problem
You are given $$$m$$$ strings and a tree on $$$n$$$ nodes. Each edge has some letter written on it.

You have to answer $$$q$$$ queries. Each query is described by $$$4$$$ integers $$$u$$$, $$$v$$$, $$$l$$$ and $$$r$$$. The answer to the query is the total number of occurrences of $$$str(u,v)$$$ in strings with indices from $$$l$$$ to $$$r$$$. $$$str(u,v)$$$ is defined as the string that is made by concatenating letters written on the edges on the shortest path from $$$u$$$ to $$$v$$$ (in order that they are traversed).

## Input Format
The first line of the input contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le m,q \le 10^5$$$).

The $$$i$$$-th of the following $$$n-1$$$ lines contains two integers $$$u_i, v_i$$$ and a lowercase Latin letter $$$c_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$), denoting the edge between nodes $$$u_i, v_i$$$ with a character $$$c_i$$$ on it.

It's guaranteed that these edges form a tree.

The following $$$m$$$ lines contain the strings consisting of lowercase Latin letters. The total length of those strings does not exceed $$$10^5$$$.

Then $$$q$$$ lines follow, each containing four integers $$$u$$$, $$$v$$$, $$$l$$$ and $$$r$$$ ($$$1 \le u,v \le n$$$, $$$u \neq v$$$, $$$1 \le l \le r \le m$$$), denoting the queries.

## Output Format
For each query print a single integer — the answer to the query.

## Examples
```input
2 5 3
1 2 a
aab
abab
aaa
b
a
2 1 1 5
1 2 1 3
2 1 3 5
```
```output
8
7
4
```
-----
```input
9 5 6
1 2 a
2 7 c
1 3 b
3 4 b
4 6 b
3 5 a
5 8 b
5 9 c
ababa
cabbb
bac
bbbac
abacaba
2 7 1 4
2 5 1 5
6 3 4 4
6 9 4 5
5 7 3 5
5 3 1 5
```
```output
3
4
2
1
1
10
```

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