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
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.
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 a car race organizer and would like to arrange some races in Linear Kingdom.

Linear Kingdom has n consecutive roads spanning from left to right. The roads are numbered from 1 to n from left to right, thus the roads follow in the order of their numbers' increasing. There will be several races that may be held on these roads. Each race will use a consecutive subset of these roads. Also, each race will pay some amount of money to you if this race is held. No races overlap in time, so some roads can be used in several races.

Unfortunately, some of the roads are in a bad condition and they need repair. Each road has repair costs associated with it, you are required to pay this cost to repair the road. A race can only take place if all the roads used in the race are renovated. Your task is to repair such roads (possibly all or none) that will maximize your profit. Your profit is defined as the total money you get from the races that are held minus the total money you spent to repair the roads. Note that you may decide not to repair any road and gain zero profit.

Print the maximum profit you can gain.

## Input Format
The first line contains two single-space separated integers, n and m (1 ≤ n, m ≤ 2·105), denoting the number of roads and the number of races, respectively.

Then n lines follow, each line will contain a single non-negative integer not exceeding 109 denoting the cost to repair a road. The costs are given in order from road 1 to road n.

Finally, m lines follow. Each line is single-space-separated triplets of integers. Each triplet will be given as lb, ub, and p (1 ≤ lb ≤ ub ≤ n, 1 ≤ p ≤ 109), which means that the race these three integers describe will use all the roads from lb to ub, inclusive, and if it's held you get p.

## Output Format
Print a single integer denoting the maximum possible profit you can gain.

Please, do not use the %lld specificator to read or write 64-bit integers in C++. It is recommended to use cin, cout stream (also you may use %I64d specificator).

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

## Note
In the first sample the optimal solution is to repair roads 1, 2, 3, and 7. Three races will take place which nets you 15. The road repair costs 11, hence your profit is 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
On a random day, Neko found $$$n$$$ treasure chests and $$$m$$$ keys. The $$$i$$$-th chest has an integer $$$a_i$$$ written on it and the $$$j$$$-th key has an integer $$$b_j$$$ on it. Neko knows those chests contain the powerful mysterious green Grapes, thus Neko wants to open as many treasure chests as possible.

The $$$j$$$-th key can be used to unlock the $$$i$$$-th chest if and only if the sum of the key number and the chest number is an odd number. Formally, $$$a_i + b_j \equiv 1 \pmod{2}$$$. One key can be used to open at most one chest, and one chest can be opened at most once.

Find the maximum number of chests Neko can open.

## Input Format
The first line contains integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^5$$$) — the number of chests and the number of keys.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the numbers written on the treasure chests.

The third line contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \leq b_i \leq 10^9$$$) — the numbers written on the keys.

## Output Format
Print the maximum number of chests you can open.

## Examples
```input
5 4
9 14 6 2 11
8 4 7 20
```
```output
3
```
-----
```input
5 1
2 4 6 8 10
5
```
```output
1
```
-----
```input
1 4
10
20 30 40 50
```
```output
0
```

## Note
In the first example, one possible way to unlock $$$3$$$ chests is as follows:

- Use first key to unlock the fifth chest,
- Use third key to unlock the second chest,
- Use fourth key to unlock the first chest.

In the second example, you can use the only key to unlock any single chest (note that one key can't be used twice).

In the third example, no key can unlock the given chest.

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
Neko loves divisors. During the latest number theory lesson, he got an interesting exercise from his math teacher.

Neko has two integers $$$a$$$ and $$$b$$$. His goal is to find a non-negative integer $$$k$$$ such that the least common multiple of $$$a+k$$$ and $$$b+k$$$ is the smallest possible. If there are multiple optimal integers $$$k$$$, he needs to choose the smallest one.

Given his mathematical talent, Neko had no trouble getting Wrong Answer on this problem. Can you help him solve it?

## Input Format
The only line contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le 10^9$$$).

## Output Format
Print the smallest non-negative integer $$$k$$$ ($$$k \ge 0$$$) such that the lowest common multiple of $$$a+k$$$ and $$$b+k$$$ is the smallest possible.

If there are many possible integers $$$k$$$ giving the same value of the least common multiple, print the smallest one.

## Examples
```input
6 10
```
```output
2
```
-----
```input
21 31
```
```output
9
```
-----
```input
5 10
```
```output
0
```

## Note
In the first test, one should choose $$$k = 2$$$, as the least common multiple of $$$6 + 2$$$ and $$$10 + 2$$$ is $$$24$$$, which is the smallest least common multiple possible.

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
Neko is playing with his toys on the backyard of Aki's house. Aki decided to play a prank on him, by secretly putting catnip into Neko's toys. Unfortunately, he went overboard and put an entire bag of catnip into the toys...

It took Neko an entire day to turn back to normal. Neko reported to Aki that he saw a lot of weird things, including a trie of all correct bracket sequences of length $$$2n$$$.

The definition of correct bracket sequence is as follows:

- The empty sequence is a correct bracket sequence,
- If $$$s$$$ is a correct bracket sequence, then $$$(\,s\,)$$$ is a correct bracket sequence,
- If $$$s$$$ and $$$t$$$ are a correct bracket sequence, then $$$st$$$ is also a correct bracket sequence.

For example, the strings "(())", "()()" form a correct bracket sequence, while ")(" and "((" not.

Aki then came up with an interesting problem: What is the size of the maximum matching (the largest set of edges such that there are no two edges with a common vertex) in this trie? Since the answer can be quite large, print it modulo $$$10^9 + 7$$$.

## Input Format
The only line contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$).

## Output Format
Print exactly one integer — the size of the maximum matching in the trie. Since the answer can be quite large, print it modulo $$$10^9 + 7$$$.

## Examples
```input
1
```
```output
1
```
-----
```input
2
```
```output
3
```
-----
```input
3
```
```output
9
```

## Note
The pictures below illustrate tries in the first two examples (for clarity, the round brackets are replaced with angle brackets). The maximum matching is highlighted with blue.

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

# Problem
This problem is same as the previous one, but has larger constraints.

Aki is playing a new video game. In the video game, he will control Neko, the giant cat, to fly between planets in the Catniverse.

There are $$$n$$$ planets in the Catniverse, numbered from $$$1$$$ to $$$n$$$. At the beginning of the game, Aki chooses the planet where Neko is initially located. Then Aki performs $$$k - 1$$$ moves, where in each move Neko is moved from the current planet $$$x$$$ to some other planet $$$y$$$ such that:

- Planet $$$y$$$ is not visited yet.
- $$$1 \leq y \leq x + m$$$ (where $$$m$$$ is a fixed constant given in the input)

This way, Neko will visit exactly $$$k$$$ different planets. Two ways of visiting planets are called different if there is some index $$$i$$$ such that, the $$$i$$$-th planet visited in the first way is different from the $$$i$$$-th planet visited in the second way.

What is the total number of ways to visit $$$k$$$ planets this way? Since the answer can be quite large, print it modulo $$$10^9 + 7$$$.

## Input Format
The only line contains three integers $$$n$$$, $$$k$$$ and $$$m$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le k \le \min(n, 12)$$$, $$$1 \le m \le 4$$$) — the number of planets in the Catniverse, the number of planets Neko needs to visit and the said constant $$$m$$$.

## Output Format
Print exactly one integer — the number of different ways Neko can visit exactly $$$k$$$ planets. Since the answer can be quite large, print it modulo $$$10^9 + 7$$$.

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

## Note
In the first example, there are $$$4$$$ ways Neko can visit all the planets:

- $$$1 \rightarrow 2 \rightarrow 3$$$
- $$$2 \rightarrow 3 \rightarrow 1$$$
- $$$3 \rightarrow 1 \rightarrow 2$$$
- $$$3 \rightarrow 2 \rightarrow 1$$$

In the second example, there are $$$9$$$ ways Neko can visit exactly $$$2$$$ planets:

- $$$1 \rightarrow 2$$$
- $$$2 \rightarrow 1$$$
- $$$2 \rightarrow 3$$$
- $$$3 \rightarrow 1$$$
- $$$3 \rightarrow 2$$$
- $$$3 \rightarrow 4$$$
- $$$4 \rightarrow 1$$$
- $$$4 \rightarrow 2$$$
- $$$4 \rightarrow 3$$$

In the third example, with $$$m = 4$$$, Neko can visit all the planets in any order, so there are $$$5! = 120$$$ ways Neko can visit all the planets.

In the fourth example, Neko only visit exactly $$$1$$$ planet (which is also the planet he initially located), and there are $$$100$$$ ways to choose the starting planet for Neko.

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 a string, consisting of lowercase Latin letters.

A pair of neighbouring letters in a string is considered ugly if these letters are also neighbouring in a alphabet. For example, string "abaca" contains ugly pairs at positions $$$(1, 2)$$$ — "ab" and $$$(2, 3)$$$ — "ba". Letters 'a' and 'z' aren't considered neighbouring in a alphabet.

Can you rearrange the letters of a given string so that there are no ugly pairs? You can choose any order of the letters of the given string but you can't add any new letters or remove the existing ones. You can also leave the order the same.

If there are multiple answers, print any of them.

You also have to answer $$$T$$$ separate queries.

## Input Format
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 100$$$) — the number of queries.

Each of the next $$$T$$$ lines contains string $$$s$$$ $$$(1 \le |s| \le 100)$$$ — the string for the next query. It is guaranteed that it contains only lowercase Latin letters.

Note that in hacks you have to set $$$T = 1$$$.

## Output Format
Print $$$T$$$ lines. The $$$i$$$-th line should contain the answer to the $$$i$$$-th query.

If the answer for the $$$i$$$-th query exists, then print such a rearrangment of letters of the given string that it contains no ugly pairs. You can choose any order of the letters of the given string but you can't add any new letters or remove the existing ones. You can also leave the order the same.

If there are multiple answers, print any of them.

Otherwise print "No answer" for that query.

## Examples
```input
4
abcd
gg
codeforces
abaca
```
```output
cadb
gg
codfoerces
No answer
```

## Note
In the first example answer "bdac" is also correct.

The second example showcases the fact that only neighbouring in alphabet letters are not allowed. The same letter is ok.

There are lots of valid answers 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 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 set of points $$$x_1$$$, $$$x_2$$$, ..., $$$x_n$$$ on the number line.

Two points $$$i$$$ and $$$j$$$ can be matched with each other if the following conditions hold:

- neither $$$i$$$ nor $$$j$$$ is matched with any other point;
- $$$|x_i - x_j| \ge z$$$.

What is the maximum number of pairs of points you can match with each other?

## Input Format
The first line contains two integers $$$n$$$ and $$$z$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le z \le 10^9$$$) — the number of points and the constraint on the distance between matched points, respectively.

The second line contains $$$n$$$ integers $$$x_1$$$, $$$x_2$$$, ..., $$$x_n$$$ ($$$1 \le x_i \le 10^9$$$).

## Output Format
Print one integer — the maximum number of pairs of points you can match with each other.

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

## Note
In the first example, you may match point $$$1$$$ with point $$$2$$$ ($$$|3 - 1| \ge 2$$$), and point $$$3$$$ with point $$$4$$$ ($$$|7 - 3| \ge 2$$$).

In the second example, you may match point $$$1$$$ with point $$$3$$$ ($$$|5 - 10| \ge 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 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 tree (an undirected connected acyclic graph) consisting of $$$n$$$ vertices and $$$n - 1$$$ edges. A number is written on each edge, each number is either $$$0$$$ (let's call such edges $$$0$$$-edges) or $$$1$$$ (those are $$$1$$$-edges).

Let's call an ordered pair of vertices $$$(x, y)$$$ ($$$x \ne y$$$) valid if, while traversing the simple path from $$$x$$$ to $$$y$$$, we never go through a $$$0$$$-edge after going through a $$$1$$$-edge. Your task is to calculate the number of valid pairs in the tree.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 200000$$$) — the number of vertices in the tree.

Then $$$n - 1$$$ lines follow, each denoting an edge of the tree. Each edge is represented by three integers $$$x_i$$$, $$$y_i$$$ and $$$c_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$0 \le c_i \le 1$$$, $$$x_i \ne y_i$$$) — the vertices connected by this edge and the number written on it, respectively.

It is guaranteed that the given edges form a tree.

## Output Format
Print one integer — the number of valid pairs of vertices.

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

## Note
The picture corresponding to 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 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: 512.0 MB

# Problem
You are given a permutation $$$p$$$ of $$$n$$$ integers $$$1$$$, $$$2$$$, ..., $$$n$$$ (a permutation is an array where each element from $$$1$$$ to $$$n$$$ occurs exactly once).

Let's call some subsegment $$$p[l, r]$$$ of this permutation special if $$$p_l + p_r = \max \limits_{i = l}^{r} p_i$$$. Please calculate the number of special subsegments.

## Input Format
The first line contains one integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$p_1$$$, $$$p_2$$$, ..., $$$p_n$$$ ($$$1 \le p_i \le n$$$). All these integers are pairwise distinct.

## Output Format
Print the number of special subsegments of the given permutation.

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

## Note
Special subsegments in the first example are $$$[1, 5]$$$ and $$$[1, 3]$$$.

The only special subsegment in the second example is $$$[1, 3]$$$.

Now solve the problem and return the code.