apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

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

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

Execution time limit: 1.0 seconds
Memory limit: 1024.0 MB

# Problem
You are given a one-based array consisting of $$$N$$$ integers: $$$A_1, A_2, \cdots, A_N$$$. Initially, the value of each element is set to $$$0$$$.

There are $$$M$$$ operations (numbered from $$$1$$$ to $$$M$$$). Operation $$$i$$$ is represented by $$$\langle L_i, R_i, X_i \rangle$$$. If operation $$$i$$$ is executed, all elements $$$A_j$$$ for $$$L_i \leq j \leq R_i$$$ will be increased by $$$X_i$$$.

You have to answer $$$Q$$$ independent queries. Each query is represented by $$$\langle K, S, T \rangle$$$ which represents the following task. Choose a range $$$[l, r]$$$ satisfying $$$S \leq l \leq r \leq T$$$, and execute operations $$$l, l + 1, \dots, r$$$. The answer to the query is the maximum value of $$$A_K$$$ after the operations are executed among all possible choices of $$$l$$$ and $$$r$$$.

## Input Format
The first line consists of two integers $$$N$$$ $$$M$$$ ($$$1 \leq N, M \leq 100\,000$$$).

Each of the next $$$M$$$ lines consists of three integers $$$L_i$$$ $$$R_i$$$ $$$X_i$$$ ($$$1 \leq L_i \leq R_i \leq N; -100\,000 \leq X_i \leq 100\,000$$$).

The following line consists of an integer $$$Q$$$ ($$$1 \leq Q \leq 100\,000$$$).

Each of the next $$$Q$$$ lines consists of three integers $$$K$$$ $$$S$$$ $$$T$$$ ($$$1 \leq K \leq N; 1 \leq S \leq T \leq M$$$).

## Output Format
For each query, output in a single line, an integer which represent the answer of the query.

## Examples
```input
2 6
1 1 -50
1 2 -20
2 2 -30
1 1 60
1 2 40
2 2 10
5
1 1 6
2 1 6
1 1 3
2 1 3
1 1 2
```
```output
100
50
0
0
-20
```
-----
```input
5 3
1 3 3
2 4 -2
3 5 3
6
1 1 3
2 1 3
3 1 3
3 2 3
2 2 3
2 2 2
```
```output
3
3
4
3
0
-2
```

## Note
Explanation for the sample input/output #1

For query $$$1$$$, one of the solutions is to execute operation $$$4$$$ and $$$5$$$.

For query $$$2$$$, one of the solutions is to execute operation $$$4$$$, $$$5$$$, and $$$6$$$.

For query $$$3$$$, the only solution is to execute operation $$$3$$$.

For query $$$4$$$, the only solution is to execute operation $$$1$$$.

For query $$$6$$$, the only solution is to execute operation $$$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: 1.0 seconds
Memory limit: 1024.0 MB

# Problem
You are playing "Grid Game 2" with your friend. There is a grid with $$$10^9$$$ rows (numbered from $$$1$$$ to $$$10^9$$$) and $$$10^9$$$ columns (numbered from $$$1$$$ to $$$10^9$$$). The cell at row $$$r$$$ and column $$$c$$$ is denoted as $$$(r, c)$$$.

Each cell can have a colour of either black or white. Initially, there are exactly $$$N$$$ black cells (numbered from $$$1$$$ to $$$N$$$). Black cell $$$i$$$ is located at $$$(R_i, C_i)$$$. The rest of the cells are white.

You and your friend will alternately take turn playing on this grid, and you are playing in the first turn. In one turn, a player will choose a black cell $$$(r, c)$$$, then toggle cells $$$(r - x, c - y)$$$ for all $$$0 \leq x, y < \min(r, c)$$$. If a cell is toggled, then the cell becomes black if it was a white cell, and the cell becomes white if it was a black cell.

For example, the following illustration shows how the grid changes after a player chooses a black cell $$$(5, 4)$$$ in their turn.

A player who is unable to play on their turn, i.e. no remaining black cells, loses the game, and the opposing player wins the game. If you and your friend are playing optimally, determine who will win the game.

## Input Format
The first line consists of an integer $$$N$$$ ($$$1 \le N \le 200\,000$$$).

Each of the next $$$N$$$ lines consists of two integers $$$R_i$$$ $$$C_i$$$ ($$$1 \leq R_i, C_i \leq 10^9)$$$. For $$$1 \leq i < j \leq N$$$, $$$(R_i, C_i) \neq (R_j, C_j)$$$.

## Output Format
Output FIRST if you will win the game, or SECOND otherwise.

## Examples
```input
2
2 3
2 4
```
```output
FIRST
```
-----
```input
1
2 2
```
```output
SECOND
```
-----
```input
13
1 1
1 4
1 5
2 1
2 4
2 5
4 1
4 2
4 4
5 1
5 2
5 4
5 5
```
```output
SECOND
```

## Note
Explanation for the sample input/output #1

You can start your move by choosing $$$(2, 4)$$$, whose effect was demonstrated in the following illustration.

The remaining black cells are $$$(1, 3)$$$ and $$$(1, 4)$$$, each of which will only toggle itself when chosen. Whichever your friend chooses on the next move, the you can choose the remaining black cell.

Explanation for the sample input/output #2

You have only one cell to choose, and will toggle cells $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(2, 1)$$$, and $$$(2, 2)$$$. Your friend and you will alternately choose the remaining black cells with your friend choosing the last black cell.

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 1024.0 MB

# Problem
You meet two new friends who are twins. The name of the elder twin is $$$A$$$, which consists of $$$N$$$ characters. While the name of the younger twin is $$$B$$$, which consists of $$$M$$$ characters. It is known that $$$N \leq M$$$.

You want to call each of them with a nickname. For the elder twin, you want to pick any permutation of $$$A$$$ as the nickname. For the younger twin, you want to remove exactly $$$M - N$$$ characters from any permutation of $$$B$$$. Denote the nicknames of the elder twin and the younger twin as $$$A'$$$ and $$$B'$$$, respectively.

You want the nicknames to satisfy the following requirement. For each $$$i$$$ that satisfies $$$1 \leq i \leq N$$$, $$$B'_i$$$ must be equal to either $$$A'_i$$$ or the next letter that follows alphabetically after $$$A'_i$$$ (if such a next letter exists).

Determine the number of different pairs of nicknames $$$(A', B')$$$ that satisfy the requirement. Two pairs of nicknames are considered different if at least one of the nicknames are different. As the result might be large, find the answer modulo $$$998\,244\,353$$$.

## Input Format
The first line consists of two integers $$$N$$$ $$$M$$$ ($$$1 \leq N \leq M \leq 200\,000$$$).

The second line consists of a string $$$A$$$ of length $$$N$$$.

The third line consists of a string $$$B$$$ of length $$$M$$$.

All strings consist of only upper-case letters.

## Output Format
Output a single integer representing number of different pairs $$$(A', B')$$$ that satisfy the requirement, modulo $$$998\,244\,353$$$.

## Examples
```input
3 4
AMA
ANAB
```
```output
9
```
-----
```input
5 8
BINUS
BINANUSA
```
```output
120
```
-----
```input
15 30
BINUSUNIVERSITY
BINANUSANTARAUNIVERSITYJAKARTA
```
```output
151362308
```
-----
```input
4 4
UDIN
ASEP
```
```output
0
```

## Note
Explanation for the sample input/output #1

The $$$9$$$ pairs are:

- (AAM, AAN),
- (AAM, ABN),
- (AAM, BAN),
- (AMA, ANA),
- (AMA, ANB),
- (AMA, BNA),
- (MAA, NAA),
- (MAA, NAB), and
- (MAA, NBA).

Explanation for the sample input/output #2

The $$$120$$$ pairs are the pairs where $$$A'$$$ is a permutation of BINUS and $$$B' = A'$$$.

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 1024.0 MB

# Problem
You are currently researching a graph traversal algorithm called the Breadth First Search (BFS). Suppose you have an input graph of $$$N$$$ nodes (numbered from $$$1$$$ to $$$N$$$). The graph is represented by an adjacency matrix $$$M$$$, for which node $$$u$$$ can traverse to node $$$v$$$ if $$$M_{u, v}$$$ is $$$1$$$, otherwise it is $$$0$$$. Your algorithm will output the order the nodes are visited in the BFS. The pseudocode of the algorithm is presented as follows.

During your research, you are interested in the following problem. Given an array $$$A$$$ such that $$$A$$$ is a permutation of $$$1$$$ to $$$N$$$ and $$$A_1 = 1$$$. How many simple undirected graph with $$$N$$$ nodes and adjacency matrix $$$M$$$ such that $$$\text{BFS}(M) = A$$$? Since the answer can be very large, calculate the answer modulo $$$998\,244\,353$$$.

A simple graph has no self-loop ($$$M_{i, i} = 0$$$ for $$$1 \leq i \leq N$$$) and there is at most one edge that connects a pair of nodes. In an undirected graph, if node $$$u$$$ is adjacent to node $$$v$$$, then node $$$v$$$ is also adjacent to node $$$u$$$; formally, $$$M_{u, v} = M_{v, u}$$$ for $$$1 \leq u < v \leq N$$$.

Two graphs are considered different if there is an edge that exists in one graph but not the other. In other words, two graphs are considered different if their adjacency matrices are different.

## Input Format
The first line consists of an integer $$$N$$$ ($$$2 \leq N \leq 5000$$$).

The second line consists of $$$N$$$ integers $$$A_i$$$. The array $$$A$$$ is a permutation of $$$1$$$ to $$$N$$$ and $$$A_1 = 1$$$.

## Output Format
Output an integer representing the number of simple undirected graphs with $$$N$$$ nodes and adjacency matrix $$$M$$$ such that $$$\text{BFS}(M) = A$$$. Since the answer can be very large, output the answer modulo $$$998\,244\,353$$$.

## Examples
```input
3
1 2 3
```
```output
3
```
-----
```input
3
1 3 2
```
```output
1
```
-----
```input
5
1 3 2 4 5
```
```output
17
```
-----
```input
11
1 2 3 4 5 6 7 8 9 10 11
```
```output
379394847
```

## Note
Explanation for the sample input/output #1

The following illustration shows all graphs that satisfy the requirements.

Explanation for the sample input/output #2

The only graph that satisfies the requirements is a graph with two edges: one that connects nodes $$$1$$$ and $$$3$$$, and another one that connects nodes $$$3$$$ and $$$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: 1.0 seconds
Memory limit: 1024.0 MB

# Problem
Construct a parentheses sequence consisting of $$$N$$$ characters such that it is balanced and the length of its longest palindromic subsequence (LPS) is exactly $$$K$$$. Determine whether such a construction is possible. If there are several possible sequences, construct any of them.

A parentheses sequence consists of only character ( and ). A parentheses sequence is balanced if each character ( has a corresponding character ) and the pairs of parentheses are properly nested. For example, (), (()), (())(), and ((())()) are balanced. However, )(, ((), and ()) are not balanced.

A sequence is palindromic if it reads the same backwards as forwards. For example, ((, ), ())(, and (()(( are palindromic. However, (), )(, and (()) are not palindromic.

A subsequence can be derived from another sequence by removing zero or more characters without changing the order of the remaining characters. For example, (, ))), ())(, and (())() are subsequence of (())(). However, )(( and ((())) are not subsequence of (())().

The longest palindromic subsequence (LPS) of a sequence is a subsequence with the maximum number of characters, derived from that sequence and it is palindromic. For example, the LPS of sequence (())() is ())(, which can be obtained by removing the second and sixth characters. Therefore, the length of the LPS of (())() is $$$4$$$.

## Input Format
Input consists of two integers $$$N$$$ $$$K$$$ ($$$2 \leq N \leq 2000; 1 \leq K \leq N$$$). $$$N$$$ is an even number.

## Output Format
If there is no such parentheses sequence such that it is balanced and the length of its LPS is exactly $$$K$$$, then output -1.

Otherwise, output a string of $$$N$$$ characters, representing the parentheses sequence. If there are several possible answers, output any of them.

## Examples
```input
6 4
```
```output
(())()
```
-----
```input
6 3
```
```output
(()())
```
-----
```input
4 1
```
```output
-1
```
-----
```input
14 11
```
```output
()((())()())()
```

## Note
Explanation for the sample input/output #2

The LPS of (()()) is either ((( by removing all ) characters, or ))) by removing all ( characters.

The output ((())) also satisfies the requirements.

Explanation for the sample input/output #3

The only possible balanced parentheses sequences are (()) and ()(). The length of the LPS of (()) and ()() are $$$2$$$ and $$$3$$$, respectively.

Explanation for the sample input/output #4

The LPS of ()((())()())() is )())()())(), which can be obtained by removing the first, fourth, and fifth characters.

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 1024.0 MB

# Problem
You are given a regular $$$N$$$-sided polygon. Label one arbitrary side as side $$$1$$$, then label the next sides in clockwise order as side $$$2$$$, $$$3$$$, $$$\dots$$$, $$$N$$$. There are $$$A_i$$$ special points on side $$$i$$$. These points are positioned such that side $$$i$$$ is divided into $$$A_i + 1$$$ segments with equal length.

For instance, suppose that you have a regular $$$4$$$-sided polygon, i.e., a square. The following illustration shows how the special points are located within each side when $$$A = [3, 1, 4, 6]$$$. The uppermost side is labelled as side $$$1$$$.

You want to create as many non-degenerate triangles as possible while satisfying the following requirements. Each triangle consists of $$$3$$$ distinct special points (not necessarily from different sides) as its corners. Each special point can only become the corner of at most $$$1$$$ triangle. All triangles must not intersect with each other.

Determine the maximum number of non-degenerate triangles that you can create.

A triangle is non-degenerate if it has a positive area.

## Input Format
The first line consists of an integer $$$N$$$ ($$$3 \leq N \leq 200\,000$$$).

The following line consists of $$$N$$$ integers $$$A_i$$$ ($$$1 \leq A_i \leq 2 \cdot 10^9$$$).

## Output Format
Output a single integer representing the maximum number of non-degenerate triangles that you can create.

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

## Note
Explanation for the sample input/output #1

One possible construction which achieves maximum number of non-degenerate triangles can be seen in the following illustration.

Explanation for the sample input/output #2

One possible construction which achieves maximum number of non-degenerate triangles can be seen in the following illustration.

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
There is a ribbon divided into $$$n$$$ cells, numbered from $$$1$$$ to $$$n$$$ from left to right. Each cell either contains a chip or is free.

You can perform the following operation any number of times (possibly zero): choose a chip and move it to the closest free cell to the left. You can choose any chip that you want, provided that there is at least one free cell to the left of it. When you move the chip, the cell where it was before the operation becomes free.

Your goal is to move the chips in such a way that they form a single block, without any free cells between them. What is the minimum number of operations you have to perform?

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

Each test case consists of two lines:

- the first line contains one integer $$$n$$$ ($$$2 \le n \le 50$$$) — the number of cells;
- the second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 1$$$); $$$a_i = 0$$$ means that the $$$i$$$-th cell is free; $$$a_i = 1$$$ means that the $$$i$$$-th cell contains a chip.

Additional constraint on the input: in each test case, at least one cell contains a chip.

## Output Format
For each test case, print one integer — the minimum number of operations you have to perform so that all chips form a single block without any free cells between them.

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

## Note
In the first example, you can perform the operation on the chip in the $$$7$$$-th cell. The closest free cell to the left is the $$$5$$$-th cell, so it moves there. After that, all chips form a single block.

In the second example, all chips are already in a single block. Same for the third 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
An array $$$a$$$ of length $$$m$$$ is considered good if there exists an integer array $$$b$$$ of length $$$m$$$ such that the following conditions hold:

1. $$$\sum\limits_{i=1}^{m} a_i = \sum\limits_{i=1}^{m} b_i$$$;
2. $$$a_i \neq b_i$$$ for every index $$$i$$$ from $$$1$$$ to $$$m$$$;
3. $$$b_i > 0$$$ for every index $$$i$$$ from $$$1$$$ to $$$m$$$.

You are given an array $$$c$$$ of length $$$n$$$. Each element of this array is greater than $$$0$$$.

You have to answer $$$q$$$ queries. During the $$$i$$$-th query, you have to determine whether the subarray $$$c_{l_{i}}, c_{l_{i}+1}, \dots, c_{r_{i}}$$$ is good.

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

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$) — the length of the array $$$c$$$ and the number of queries.

The second line of each test case contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^9$$$).

Then $$$q$$$ lines follow. The $$$i$$$-th of them contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — the borders of the $$$i$$$-th subarray.

Additional constraints on the input: the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$; the sum of $$$q$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

## Output Format
For each query, print YES if the subarray is good. Otherwise, print NO.

You can output each letter of the answer in any case (upper or lower). For example, the strings yEs, yes, Yes, and YES will all be recognized as positive responses.

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

Now solve the problem and return the code.