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
Petr has just bought a new car. He's just arrived at the most known Petersburg's petrol station to refuel it when he suddenly discovered that the petrol tank is secured with a combination lock! The lock has a scale of $$$360$$$ degrees and a pointer which initially points at zero:

Petr called his car dealer, who instructed him to rotate the lock's wheel exactly $$$n$$$ times. The $$$i$$$-th rotation should be $$$a_i$$$ degrees, either clockwise or counterclockwise, and after all $$$n$$$ rotations the pointer should again point at zero.

This confused Petr a little bit as he isn't sure which rotations should be done clockwise and which should be done counterclockwise. As there are many possible ways of rotating the lock, help him and find out whether there exists at least one, such that after all $$$n$$$ rotations the pointer will point at zero again.

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \leq n \leq 15$$$) — the number of rotations.

Each of the following $$$n$$$ lines contains one integer $$$a_i$$$ ($$$1 \leq a_i \leq 180$$$) — the angle of the $$$i$$$-th rotation in degrees.

## Output Format
If it is possible to do all the rotations so that the pointer will point at zero after all of them are performed, print a single word "YES". Otherwise, print "NO". Petr will probably buy a new car in this case.

You can print each letter in any case (upper or lower).

## Examples
```input
3
10
20
30
```
```output
YES
```
-----
```input
3
10
10
10
```
```output
NO
```
-----
```input
3
120
120
120
```
```output
YES
```

## Note
In the first example, we can achieve our goal by applying the first and the second rotation clockwise, and performing the third rotation counterclockwise.

In the second example, it's impossible to perform the rotations in order to make the pointer point at zero in the end.

In the third example, Petr can do all three rotations clockwise. In this case, the whole wheel will be rotated by $$$360$$$ degrees clockwise and the pointer will point at zero again.

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
One day, Yuhao came across a problem about checking if some bracket sequences are correct bracket sequences.

A bracket sequence is any non-empty sequence of opening and closing parentheses. A bracket sequence is called a correct bracket sequence if it's possible to obtain a correct arithmetic expression by inserting characters "+" and "1" into this sequence. For example, the sequences "(())()", "()" and "(()(()))" are correct, while the bracket sequences ")(", "(()" and "(()))(" are not correct.

Yuhao found this problem too simple for him so he decided to make the problem harder. You are given many (not necessarily correct) bracket sequences. The task is to connect some of them into ordered pairs so that each bracket sequence occurs in at most one pair and the concatenation of the bracket sequences in each pair is a correct bracket sequence. The goal is to create as many pairs as possible.

This problem unfortunately turned out to be too difficult for Yuhao. Can you help him and solve it?

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of bracket sequences.

Each of the following $$$n$$$ lines contains one bracket sequence — a non-empty string which consists only of characters "(" and ")".

The sum of lengths of all bracket sequences in the input is at most $$$5 \cdot 10^5$$$.

Note that a bracket sequence may appear in the input multiple times. In this case, you can use each copy of the sequence separately. Also note that the order in which strings appear in the input doesn't matter.

## Output Format
Print a single integer — the maximum number of pairs which can be made, adhering to the conditions in the statement.

## Examples
```input
7
)())
)
((
((
(
)
)
```
```output
2
```
-----
```input
4
(
((
(((
(())
```
```output
0
```
-----
```input
2
(())
()
```
```output
1
```

## Note
In the first example, it's optimal to construct two pairs: "((     )())" and "(     )".

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
Makoto has a big blackboard with a positive integer $$$n$$$ written on it. He will perform the following action exactly $$$k$$$ times:

Suppose the number currently written on the blackboard is $$$v$$$. He will randomly pick one of the divisors of $$$v$$$ (possibly $$$1$$$ and $$$v$$$) and replace $$$v$$$ with this divisor. As Makoto uses his famous random number generator (RNG) and as he always uses $$$58$$$ as his generator seed, each divisor is guaranteed to be chosen with equal probability.

He now wonders what is the expected value of the number written on the blackboard after $$$k$$$ steps.

It can be shown that this value can be represented as $$$\frac{P}{Q}$$$ where $$$P$$$ and $$$Q$$$ are coprime integers and $$$Q \not\equiv 0 \pmod{10^9+7}$$$. Print the value of $$$P \cdot Q^{-1}$$$ modulo $$$10^9+7$$$.

## Input Format
The only line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^{15}$$$, $$$1 \leq k \leq 10^4$$$).

## Output Format
Print a single integer — the expected value of the number on the blackboard after $$$k$$$ steps as $$$P \cdot Q^{-1} \pmod{10^9+7}$$$ for $$$P$$$, $$$Q$$$ defined above.

## Examples
```input
6 1
```
```output
3
```
-----
```input
6 2
```
```output
875000008
```
-----
```input
60 5
```
```output
237178099
```

## Note
In the first example, after one step, the number written on the blackboard is $$$1$$$, $$$2$$$, $$$3$$$ or $$$6$$$ — each occurring with equal probability. Hence, the answer is $$$\frac{1+2+3+6}{4}=3$$$.

In the second example, the answer is equal to $$$1 \cdot \frac{9}{16}+2 \cdot \frac{3}{16}+3 \cdot \frac{3}{16}+6 \cdot \frac{1}{16}=\frac{15}{8}$$$.

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

# Problem
A great legend used to be here, but some troll hacked Codeforces and erased it. Too bad for us, but in the troll society he earned a title of an ultimate-greatest-over troll. At least for them, it's something good. And maybe a formal statement will be even better for us?

You are given a tree $$$T$$$ with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. For every non-empty subset $$$X$$$ of vertices of $$$T$$$, let $$$f(X)$$$ be the minimum number of edges in the smallest connected subtree of $$$T$$$ which contains every vertex from $$$X$$$.

You're also given an integer $$$k$$$. You need to compute the sum of $$$(f(X))^k$$$ among all non-empty subsets of vertices, that is:

$$$$$$ \sum\limits_{X \subseteq \{1, 2,\: \dots \:, n\},\, X \neq \varnothing} (f(X))^k. $$$$$$

As the result might be very large, output it modulo $$$10^9 + 7$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq k \leq 200$$$) — the size of the tree and the exponent in the sum above.

Each of the following $$$n - 1$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i,b_i \leq n$$$) — the indices of the vertices connected by the corresponding edge.

It is guaranteed, that the edges form a tree.

## Output Format
Print a single integer — the requested sum modulo $$$10^9 + 7$$$.

## Examples
```input
4 1
1 2
2 3
2 4
```
```output
21
```
-----
```input
4 2
1 2
2 3
2 4
```
```output
45
```
-----
```input
5 3
1 2
2 3
3 4
4 5
```
```output
780
```

## Note
In the first two examples, the values of $$$f$$$ are as follows:

$$$f(\{1\}) = 0$$$

$$$f(\{2\}) = 0$$$

$$$f(\{1, 2\}) = 1$$$

$$$f(\{3\}) = 0$$$

$$$f(\{1, 3\}) = 2$$$

$$$f(\{2, 3\}) = 1$$$

$$$f(\{1, 2, 3\}) = 2$$$

$$$f(\{4\}) = 0$$$

$$$f(\{1, 4\}) = 2$$$

$$$f(\{2, 4\}) = 1$$$

$$$f(\{1, 2, 4\}) = 2$$$

$$$f(\{3, 4\}) = 2$$$

$$$f(\{1, 3, 4\}) = 3$$$

$$$f(\{2, 3, 4\}) = 2$$$

$$$f(\{1, 2, 3, 4\}) = 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Lunar New Year is approaching, and you bought a matrix with lots of "crosses".

This matrix $$$M$$$ of size $$$n \times n$$$ contains only 'X' and '.' (without quotes). The element in the $$$i$$$-th row and the $$$j$$$-th column $$$(i, j)$$$ is defined as $$$M(i, j)$$$, where $$$1 \leq i, j \leq n$$$. We define a cross appearing in the $$$i$$$-th row and the $$$j$$$-th column ($$$1 < i, j < n$$$) if and only if $$$M(i, j) = M(i - 1, j - 1) = M(i - 1, j + 1) = M(i + 1, j - 1) = M(i + 1, j + 1) = $$$ 'X'.

The following figure illustrates a cross appearing at position $$$(2, 2)$$$ in a $$$3 \times 3$$$ matrix.

X.X.X.X.X

Your task is to find out the number of crosses in the given matrix $$$M$$$. Two crosses are different if and only if they appear in different rows or columns.

## Input Format
The first line contains only one positive integer $$$n$$$ ($$$1 \leq n \leq 500$$$), denoting the size of the matrix $$$M$$$.

The following $$$n$$$ lines illustrate the matrix $$$M$$$. Each line contains exactly $$$n$$$ characters, each of them is 'X' or '.'. The $$$j$$$-th element in the $$$i$$$-th line represents $$$M(i, j)$$$, where $$$1 \leq i, j \leq n$$$.

## Output Format
Output a single line containing only one integer number $$$k$$$ — the number of crosses in the given matrix $$$M$$$.

## Examples
```input
5
.....
.XXX.
.XXX.
.XXX.
.....
```
```output
1
```
-----
```input
2
XX
XX
```
```output
0
```
-----
```input
6
......
X.X.X.
.X.X.X
X.X.X.
.X.X.X
......
```
```output
4
```

## Note
In the first sample, a cross appears at $$$(3, 3)$$$, so the answer is $$$1$$$.

In the second sample, no crosses appear since $$$n < 3$$$, so the answer is $$$0$$$.

In the third sample, crosses appear at $$$(3, 2)$$$, $$$(3, 4)$$$, $$$(4, 3)$$$, $$$(4, 5)$$$, so the answer 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 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
Little Petya loves presents. His mum bought him two strings of the same size for his birthday. The strings consist of uppercase and lowercase Latin letters. Now Petya wants to compare those two strings lexicographically. The letters' case does not matter, that is an uppercase letter is considered equivalent to the corresponding lowercase letter. Help Petya perform the comparison.

## Input Format
Each of the first two lines contains a bought string. The strings' lengths range from 1 to 100 inclusive. It is guaranteed that the strings are of the same length and also consist of uppercase and lowercase Latin letters.

## Output Format
If the first string is less than the second one, print "-1". If the second string is less than the first one, print "1". If the strings are equal, print "0". Note that the letters' case is not taken into consideration when the strings are compared.

## Examples
```input
aaaa
aaaA
```
```output
0
```
-----
```input
abs
Abz
```
```output
-1
```
-----
```input
abcdefg
AbCdEfF
```
```output
1
```

## Note
If you want more formal information about the lexicographical order (also known as the "dictionary order" or "alphabetical order"), you can visit the following site:

- http://en.wikipedia.org/wiki/Lexicographical_order

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
Little Petya loves playing with squares. Mum bought him a square 2n × 2n in size. Petya marked a cell inside the square and now he is solving the following task.

The task is to draw a broken line that would go along the grid lines and that would cut the square into two equal parts. The cutting line should not have any common points with the marked cell and the resulting two parts should be equal up to rotation.

Petya wants to determine whether it is possible to cut the square in the required manner given the sizes of the square side and the coordinates of the marked cell. Help him.

## Input Format
The first line contains three space-separated integers 2n, x and y (2 ≤ 2n ≤ 100, 1 ≤ x, y ≤ 2n), representing the length of a square's side and the coordinates of the marked cell. It is guaranteed that 2n is even.

The coordinates of the marked cell are represented by a pair of numbers x y, where x represents the number of the row and y represents the number of the column. The rows and columns are numbered by consecutive integers from 1 to 2n. The rows are numbered from top to bottom and the columns are numbered from the left to the right.

## Output Format
If the square is possible to cut, print "YES", otherwise print "NO" (without the quotes).

## Examples
```input
4 1 1
```
```output
YES
```
-----
```input
2 2 2
```
```output
NO
```

## Note
A sample test from the statement and one of the possible ways of cutting the square are shown in the picture:

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 bracket sequence if it does not contain any characters other than "(" and ")". A bracket sequence is called regular if it it is possible to obtain correct arithmetic expression by inserting characters "+" and "1" into this sequence. For example, "", "(())" and "()()" are regular bracket sequences; "))" and ")((" are bracket sequences (but not regular ones), and "(a)" and "(1)+(1)" are not bracket sequences at all.

You have a number of strings; each string is a bracket sequence of length $$$2$$$. So, overall you have $$$cnt_1$$$ strings "((", $$$cnt_2$$$ strings "()", $$$cnt_3$$$ strings ")(" and $$$cnt_4$$$ strings "))". You want to write all these strings in some order, one after another; after that, you will get a long bracket sequence of length $$$2(cnt_1 + cnt_2 + cnt_3 + cnt_4)$$$. You wonder: is it possible to choose some order of the strings you have such that you will get a regular bracket sequence? Note that you may not remove any characters or strings, and you may not add anything either.

## Input Format
The input consists of four lines, $$$i$$$-th of them contains one integer $$$cnt_i$$$ ($$$0 \le cnt_i \le 10^9$$$).

## Output Format
Print one integer: $$$1$$$ if it is possible to form a regular bracket sequence by choosing the correct order of the given strings, $$$0$$$ otherwise.

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

## Note
In the first example it is possible to construct a string "(())()(()((()()()())))", which is a regular bracket sequence.

In the second example it is possible to construct a string "", which is a regular bracket sequence.

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

# Problem
You came to a local shop and want to buy some chocolate bars. There are $$$n$$$ bars in the shop, $$$i$$$-th of them costs $$$a_i$$$ coins (and you want to buy all of them).

You have $$$m$$$ different coupons that allow you to buy chocolate bars. $$$i$$$-th coupon allows you to buy $$$q_i$$$ chocolate bars while you have to pay only for the $$$q_i - 1$$$ most expensive ones (so, the cheapest bar of those $$$q_i$$$ bars is for free).

You can use only one coupon; if you use coupon $$$i$$$, you have to choose $$$q_i$$$ bars and buy them using the coupon, and buy all the remaining $$$n - q_i$$$ bars without any discounts.

To decide which coupon to choose, you want to know what will be the minimum total amount of money you have to pay if you use one of the coupons optimally.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — the number of chocolate bars in the shop.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the cost of $$$i$$$-th chocolate bar.

The third line contains one integer $$$m$$$ ($$$1 \le m \le n - 1$$$) — the number of coupons you have.

The fourth line contains $$$m$$$ integers $$$q_1$$$, $$$q_2$$$, ..., $$$q_m$$$ ($$$2 \le q_i \le n$$$), where $$$q_i$$$ is the number of chocolate bars you have to buy using $$$i$$$-th coupon so that the least expensive of them will be for free. All values of $$$q_i$$$ are pairwise distinct.

## Output Format
Print $$$m$$$ integers, $$$i$$$-th of them should be the minimum amount of money you have to pay if you buy $$$q_i$$$ bars with $$$i$$$-th coupon, and all the remaining bars one by one for their full price.

## Examples
```input
7
7 1 3 1 4 10 8
2
3 4
```
```output
27
30
```

## Note
Consider the first example.

If we use the first coupon, we may choose chocolate bars having indices $$$1$$$, $$$6$$$ and $$$7$$$, and we pay $$$18$$$ coins for them and $$$9$$$ coins for all other bars.

If we use the second coupon, we may choose chocolate bars having indices $$$1$$$, $$$5$$$, $$$6$$$ and $$$7$$$, and we pay $$$25$$$ coins for them and $$$5$$$ coins for all other bars.

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 have a long fence which consists of $$$n$$$ sections. Unfortunately, it is not painted, so you decided to hire $$$q$$$ painters to paint it. $$$i$$$-th painter will paint all sections $$$x$$$ such that $$$l_i \le x \le r_i$$$.

Unfortunately, you are on a tight budget, so you may hire only $$$q - 2$$$ painters. Obviously, only painters you hire will do their work.

You want to maximize the number of painted sections if you choose $$$q - 2$$$ painters optimally. A section is considered painted if at least one painter paints it.

## Input Format
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$3 \le n, q \le 5000$$$) — the number of sections and the number of painters availible for hire, respectively.

Then $$$q$$$ lines follow, each describing one of the painters: $$$i$$$-th line contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$).

## Output Format
Print one integer — maximum number of painted sections if you hire $$$q - 2$$$ painters.

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

Now solve the problem and return the code.