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

# Problem
Alyona has recently bought a miniature fridge that can be represented as a matrix with $$$h$$$ rows and $$$2$$$ columns. Initially there is only one shelf at the bottom of the fridge, but Alyona can install arbitrary number of shelves inside the fridge between any two rows. A shelf is two cells wide, does not occupy any space but separates the inside of the fridge to the lower and upper part.

An example of a fridge with $$$h = 7$$$ and two shelves. The shelves are shown in black. The picture corresponds to the first example.

Alyona has $$$n$$$ bottles of milk that she wants to put in the fridge. The $$$i$$$-th bottle is $$$a_i$$$ cells tall and $$$1$$$ cell wide. She can put a bottle on some shelf if the corresponding space above the shelf is at least as tall as the bottle. She can not put a bottle on top of another bottle (if there is no shelf between them). Two bottles can not share a cell.

Alyona is interested in the largest integer $$$k$$$ such that she can put bottles $$$1$$$, $$$2$$$, ..., $$$k$$$ in the fridge at the same time. Find this largest $$$k$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$h$$$ ($$$1 \le n \le 10^3$$$, $$$1 \le h \le 10^9$$$) — the number of bottles and the height of the fridge.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le h$$$) — the heights of the bottles.

## Output Format
Print the single integer $$$k$$$ — the maximum integer such that Alyona can put the bottles $$$1$$$, $$$2$$$, ..., $$$k$$$ in the fridge at the same time. If Alyona can put all bottles in the fridge, print $$$n$$$. It is easy to see that Alyona can always put at least one bottle in the fridge.

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

## Note
One of optimal locations in the first example is shown on the picture in the statement.

One of optimal locations in the second example is shown on the picture below.

One of optimal locations in the third example is shown on the picture below.

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
Pavel has several sticks with lengths equal to powers of two.

He has $$$a_0$$$ sticks of length $$$2^0 = 1$$$, $$$a_1$$$ sticks of length $$$2^1 = 2$$$, ..., $$$a_{n-1}$$$ sticks of length $$$2^{n-1}$$$.

Pavel wants to make the maximum possible number of triangles using these sticks. The triangles should have strictly positive area, each stick can be used in at most one triangle.

It is forbidden to break sticks, and each triangle should consist of exactly three sticks.

Find the maximum possible number of triangles.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 300\,000$$$) — the number of different lengths of sticks.

The second line contains $$$n$$$ integers $$$a_0$$$, $$$a_1$$$, ..., $$$a_{n-1}$$$ ($$$1 \leq a_i \leq 10^9$$$), where $$$a_i$$$ is the number of sticks with the length equal to $$$2^i$$$.

## Output Format
Print a single integer — the maximum possible number of non-degenerate triangles that Pavel can make.

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

## Note
In the first example, Pavel can, for example, make this set of triangles (the lengths of the sides of the triangles are listed): $$$(2^0, 2^4, 2^4)$$$, $$$(2^1, 2^3, 2^3)$$$, $$$(2^1, 2^2, 2^2)$$$.

In the second example, Pavel cannot make a single triangle.

In the third example, Pavel can, for example, create this set of triangles (the lengths of the sides of the triangles are listed): $$$(2^0, 2^0, 2^0)$$$, $$$(2^1, 2^1, 2^1)$$$, $$$(2^2, 2^2, 2^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.5 seconds
Memory limit: 256.0 MB

# Problem
You have received your birthday gifts — $$$n$$$ triples of integers! The $$$i$$$-th of them is $$$\lbrace a_{i}, b_{i}, c_{i} \rbrace$$$. All numbers are greater than or equal to $$$0$$$, and strictly smaller than $$$2^{k}$$$, where $$$k$$$ is a fixed integer.

One day, you felt tired playing with triples. So you came up with three new integers $$$x$$$, $$$y$$$, $$$z$$$, and then formed $$$n$$$ arrays. The $$$i$$$-th array consists of $$$a_i$$$ repeated $$$x$$$ times, $$$b_i$$$ repeated $$$y$$$ times and $$$c_i$$$ repeated $$$z$$$ times. Thus, each array has length $$$(x + y + z)$$$.

You want to choose exactly one integer from each array such that the XOR (bitwise exclusive or) of them is equal to $$$t$$$. Output the number of ways to choose the numbers for each $$$t$$$ between $$$0$$$ and $$$2^{k} - 1$$$, inclusive, modulo $$$998244353$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^{5}$$$, $$$1 \leq k \leq 17$$$) — the number of arrays and the binary length of all numbers.

The second line contains three integers $$$x$$$, $$$y$$$, $$$z$$$ ($$$0 \leq x,y,z \leq 10^{9}$$$) — the integers you chose.

Then $$$n$$$ lines follow. The $$$i$$$-th of them contains three integers $$$a_{i}$$$, $$$b_{i}$$$ and $$$c_{i}$$$ ($$$0 \leq a_{i} , b_{i} , c_{i} \leq 2^{k} - 1$$$) — the integers forming the $$$i$$$-th array.

## Output Format
Print a single line containing $$$2^{k}$$$ integers. The $$$i$$$-th of them should be the number of ways to choose exactly one integer from each array so that their XOR is equal to $$$t = i-1$$$ modulo $$$998244353$$$.

## Examples
```input
1 1
1 2 3
1 0 1
```
```output
2 4
```
-----
```input
2 2
1 2 1
0 1 2
1 2 3
```
```output
4 2 4 6
```
-----
```input
4 3
1 2 3
1 3 7
0 2 5
1 0 6
3 3 2
```
```output
198 198 126 126 126 126 198 198
```

## Note
In the first example, the array we formed is $$$(1, 0, 0, 1, 1, 1)$$$, we have two choices to get $$$0$$$ as the XOR and four choices to get $$$1$$$.

In the second example, two arrays are $$$(0, 1, 1, 2)$$$ and $$$(1, 2, 2, 3)$$$. There are sixteen $$$(4 \cdot 4)$$$ choices in total, $$$4$$$ of them ($$$1 \oplus 1$$$ and $$$2 \oplus 2$$$, two options for each) give $$$0$$$, $$$2$$$ of them ($$$0 \oplus 1$$$ and $$$2 \oplus 3$$$) give $$$1$$$, $$$4$$$ of them ($$$0 \oplus 2$$$ and $$$1 \oplus 3$$$, two options for each) give $$$2$$$, and finally $$$6$$$ of them ($$$0 \oplus 3$$$, $$$2 \oplus 1$$$ and four options for $$$1 \oplus 2$$$) give $$$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 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: 256.0 MB

# Problem
You are given an array of $$$n$$$ integers: $$$a_1, a_2, \ldots, a_n$$$. Your task is to find some non-zero integer $$$d$$$ ($$$-10^3 \leq d \leq 10^3$$$) such that, after each number in the array is divided by $$$d$$$, the number of positive numbers that are presented in the array is greater than or equal to half of the array size (i.e., at least $$$\lceil\frac{n}{2}\rceil$$$). Note that those positive numbers do not need to be an integer (e.g., a $$$2.5$$$ counts as a positive number). If there are multiple values of $$$d$$$ that satisfy the condition, you may print any of them. In case that there is no such $$$d$$$, print a single integer $$$0$$$.

Recall that $$$\lceil x \rceil$$$ represents the smallest integer that is not less than $$$x$$$ and that zero ($$$0$$$) is neither positive nor negative.

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of elements in the array.

The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^3 \le a_i \le 10^3$$$).

## Output Format
Print one integer $$$d$$$ ($$$-10^3 \leq d \leq 10^3$$$ and $$$d \neq 0$$$) that satisfies the given condition. If there are multiple values of $$$d$$$ that satisfy the condition, you may print any of them. In case that there is no such $$$d$$$, print a single integer $$$0$$$.

## Examples
```input
5
10 0 -7 2 6
```
```output
4
```
-----
```input
7
0 0 1 -1 0 0 2
```
```output
0
```

## Note
In the first sample, $$$n = 5$$$, so we need at least $$$\lceil\frac{5}{2}\rceil = 3$$$ positive numbers after division. If $$$d = 4$$$, the array after division is $$$[2.5, 0, -1.75, 0.5, 1.5]$$$, in which there are $$$3$$$ positive numbers (namely: $$$2.5$$$, $$$0.5$$$, and $$$1.5$$$).

In the second sample, there is no valid $$$d$$$, so $$$0$$$ should be printed.

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

# Problem
A string is called diverse if it contains consecutive (adjacent) letters of the Latin alphabet and each letter occurs exactly once. For example, the following strings are diverse: "fced", "xyz", "r" and "dabcef". The following string are not diverse: "az", "aa", "bad" and "babc". Note that the letters 'a' and 'z' are not adjacent.

Formally, consider positions of all letters in the string in the alphabet. These positions should form contiguous segment, i.e. they should come one by one without any gaps. And all letters in the string should be distinct (duplicates are not allowed).

You are given a sequence of strings. For each string, if it is diverse, print "Yes". Otherwise, print "No".

## Input Format
The first line contains integer $$$n$$$ ($$$1 \le n \le 100$$$), denoting the number of strings to process. The following $$$n$$$ lines contains strings, one string per line. Each string contains only lowercase Latin letters, its length is between $$$1$$$ and $$$100$$$, inclusive.

## Output Format
Print $$$n$$$ lines, one line per a string in the input. The line should contain "Yes" if the corresponding string is diverse and "No" if the corresponding string is not diverse. You can print each letter in any case (upper or lower). For example, "YeS", "no" and "yES" are all acceptable.

## Examples
```input
8
fced
xyz
r
dabcef
az
aa
bad
babc
```
```output
Yes
Yes
Yes
Yes
No
No
No
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 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
Polycarp has an array $$$a$$$ consisting of $$$n$$$ integers.

He wants to play a game with this array. The game consists of several moves. On the first move he chooses any element and deletes it (after the first move the array contains $$$n-1$$$ elements). For each of the next moves he chooses any element with the only restriction: its parity should differ from the parity of the element deleted on the previous move. In other words, he alternates parities (even-odd-even-odd-... or odd-even-odd-even-...) of the removed elements. Polycarp stops if he can't make a move.

Formally:

- If it is the first move, he chooses any element and deletes it;
- If it is the second or any next move:   if the last deleted element was odd, Polycarp chooses any even element and deletes it;  if the last deleted element was even, Polycarp chooses any odd element and deletes it.
- If after some move Polycarp cannot make a move, the game ends.

Polycarp's goal is to minimize the sum of non-deleted elements of the array after end of the game. If Polycarp can delete the whole array, then the sum of non-deleted elements is zero.

Help Polycarp find this value.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 2000$$$) — the number of elements of $$$a$$$.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^6$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

## Output Format
Print one integer — the minimum possible sum of non-deleted elements of the array after end of the game.

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

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
You are given an array $$$a$$$ consisting of $$$n$$$ integers. You can perform the following operations arbitrary number of times (possibly, zero):

1. Choose a pair of indices $$$(i, j)$$$ such that $$$|i-j|=1$$$ (indices $$$i$$$ and $$$j$$$ are adjacent) and set $$$a_i := a_i + |a_i - a_j|$$$;
2. Choose a pair of indices $$$(i, j)$$$ such that $$$|i-j|=1$$$ (indices $$$i$$$ and $$$j$$$ are adjacent) and set $$$a_i := a_i - |a_i - a_j|$$$.

The value $$$|x|$$$ means the absolute value of $$$x$$$. For example, $$$|4| = 4$$$, $$$|-3| = 3$$$.

Your task is to find the minimum number of operations required to obtain the array of equal elements and print the order of operations to do it.

It is guaranteed that you always can obtain the array of equal elements using such operations.

Note that after each operation each element of the current array should not exceed $$$10^{18}$$$ by absolute value.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of elements in $$$a$$$.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2 \cdot 10^5$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

## Output Format
In the first line print one integer $$$k$$$ — the minimum number of operations required to obtain the array of equal elements.

In the next $$$k$$$ lines print operations itself. The $$$p$$$-th operation should be printed as a triple of integers $$$(t_p, i_p, j_p)$$$, where $$$t_p$$$ is either $$$1$$$ or $$$2$$$ ($$$1$$$ means that you perform the operation of the first type, and $$$2$$$ means that you perform the operation of the second type), and $$$i_p$$$ and $$$j_p$$$ are indices of adjacent elements of the array such that $$$1 \le i_p, j_p \le n$$$, $$$|i_p - j_p| = 1$$$. See the examples for better understanding.

Note that after each operation each element of the current array should not exceed $$$10^{18}$$$ by absolute value.

If there are many possible answers, you can print any.

## Examples
```input
5
2 4 6 6 6
```
```output
2
1 2 3 
1 1 2
```
-----
```input
3
2 8 10
```
```output
2
2 2 1 
2 3 2
```
-----
```input
4
1 1 1 1
```
```output
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 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
You are given a connected undirected graph consisting of $$$n$$$ vertices and $$$m$$$ edges. There are no self-loops or multiple edges in the given graph.

You have to direct its edges in such a way that the obtained directed graph does not contain any paths of length two or greater (where the length of path is denoted as the number of traversed edges).

## Input Format
The first line contains two integer numbers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$n - 1 \le m \le 2 \cdot 10^5$$$) — the number of vertices and edges, respectively.

The following $$$m$$$ lines contain edges: edge $$$i$$$ is given as a pair of vertices $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$). There are no multiple edges in the given graph, i. e. for each pair ($$$u_i, v_i$$$) there are no other pairs ($$$u_i, v_i$$$) and ($$$v_i, u_i$$$) in the list of edges. It is also guaranteed that the given graph is connected (there is a path between any pair of vertex in the given graph).

## Output Format
If it is impossible to direct edges of the given graph in such a way that the obtained directed graph does not contain paths of length at least two, print "NO" in the first line.

Otherwise print "YES" in the first line, and then print any suitable orientation of edges: a binary string (the string consisting only of '0' and '1') of length $$$m$$$. The $$$i$$$-th element of this string should be '0' if the $$$i$$$-th edge of the graph should be directed from $$$u_i$$$ to $$$v_i$$$, and '1' otherwise. Edges are numbered in the order they are given in the input.

## Examples
```input
6 5
1 5
2 1
1 4
3 1
6 1
```
```output
YES
10100
```

## Note
The picture corresponding to the first example:

And one of possible answers:

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 define an unambiguous arithmetic expression (UAE) as follows.

- All non-negative integers are UAE's. Integers may have leading zeroes (for example, 0000 and 0010 are considered valid integers).
- If X and Y are two UAE's, then "(X) + (Y)", "(X) - (Y)", "(X) * (Y)", and "(X) / (Y)" (all without the double quotes) are UAE's.
- If X is an UAE, then " - (X)" and " + (X)" (both without the double quotes) are UAE's.You are given a string consisting only of digits ("0" - "9") and characters "-", "+", "*", and "/". Your task is to compute the number of different possible unambiguous arithmetic expressions such that if all brackets (characters "(" and ")") of that unambiguous arithmetic expression are removed, it becomes the input string. Since the answer may be very large, print it modulo 1000003 (106 + 3).

## Input Format
The first line is a non-empty string consisting of digits ('0'-'9') and characters '-', '+', '*', and/or '/'. Its length will not exceed 2000. The line doesn't contain any spaces.

## Output Format
Print a single integer representing the number of different unambiguous arithmetic expressions modulo 1000003 (106 + 3) such that if all its brackets are removed, it becomes equal to the input string (character-by-character).

## Examples
```input
1+2*3
```
```output
2
```
-----
```input
03+-30+40
```
```output
3
```
-----
```input
5//4
```
```output
0
```
-----
```input
5/0
```
```output
1
```
-----
```input
1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
```
```output
100728
```

## Note
For the first example, the two possible unambiguous arithmetic expressions are:

For the second example, the three possible unambiguous arithmetic expressions are:

Now solve the problem and return the code.