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
A correct expression of the form a+b=c was written; a, b and c are non-negative integers without leading zeros. In this expression, the plus and equally signs were lost. The task is to restore the expression. In other words, one character '+' and one character '=' should be inserted into given sequence of digits so that:

- character'+' is placed on the left of character '=',
- characters '+' and '=' split the sequence into three non-empty subsequences consisting of digits (let's call the left part a, the middle part — b and the right part — c),
- all the three parts a, b and c do not contain leading zeros,
- it is true that a+b=c.

It is guaranteed that in given tests answer always exists.

## Input Format
The first line contains a non-empty string consisting of digits. The length of the string does not exceed 106.

## Output Format
Output the restored expression. If there are several solutions, you can print any of them.

Note that the answer at first should contain two terms (divided with symbol '+'), and then the result of their addition, before which symbol'=' should be.

Do not separate numbers and operation signs with spaces. Strictly follow the output format given in the examples.

If you remove symbol '+' and symbol '=' from answer string you should get a string, same as string from the input data.

## Examples
```input
12345168
```
```output
123+45=168
```
-----
```input
099
```
```output
0+9=9
```
-----
```input
199100
```
```output
1+99=100
```
-----
```input
123123123456456456579579579
```
```output
123123123+456456456=579579579
```

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

# Problem
Yakko, Wakko and Dot, world-famous animaniacs, decided to rest from acting in cartoons, and take a leave to travel a bit. Yakko dreamt to go to Pennsylvania, his Motherland and the Motherland of his ancestors. Wakko thought about Tasmania, its beaches, sun and sea. Dot chose Transylvania as the most mysterious and unpredictable place.

But to their great regret, the leave turned to be very short, so it will be enough to visit one of the three above named places. That's why Yakko, as the cleverest, came up with a truly genius idea: let each of the three roll an ordinary six-sided die, and the one with the highest amount of points will be the winner, and will take the other two to the place of his/her dreams.

Yakko thrown a die and got Y points, Wakko — W points. It was Dot's turn. But she didn't hurry. Dot wanted to know for sure what were her chances to visit Transylvania.

It is known that Yakko and Wakko are true gentlemen, that's why if they have the same amount of points with Dot, they will let Dot win.

## Input Format
The only line of the input file contains two natural numbers Y and W — the results of Yakko's and Wakko's die rolls.

## Output Format
Output the required probability in the form of irreducible fraction in format «A/B», where A — the numerator, and B — the denominator. If the required probability equals to zero, output «0/1». If the required probability equals to 1, output «1/1».

## Examples
```input
4 2
```
```output
1/2
```

## Note
Dot will go to Transylvania, if she is lucky to roll 4, 5 or 6 points.

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

# Problem
And again a misfortune fell on Poor Student. He is being late for an exam.

Having rushed to a bus stop that is in point (0, 0), he got on a minibus and they drove along a straight line, parallel to axis OX, in the direction of increasing x.

Poor Student knows the following:

- during one run the minibus makes n stops, the i-th stop is in point (xi, 0)
- coordinates of all the stops are different
- the minibus drives at a constant speed, equal to vb
- it can be assumed the passengers get on and off the minibus at a bus stop momentarily
- Student can get off the minibus only at a bus stop
- Student will have to get off the minibus at a terminal stop, if he does not get off earlier
- the University, where the exam will be held, is in point (xu, yu)
- Student can run from a bus stop to the University at a constant speed vs as long as needed
- a distance between two points can be calculated according to the following formula: $$\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}$$
- Student is already on the minibus, so, he cannot get off at the first bus stop

Poor Student wants to get to the University as soon as possible. Help him to choose the bus stop, where he should get off. If such bus stops are multiple, choose the bus stop closest to the University.

## Input Format
The first line contains three integer numbers: 2 ≤ n ≤ 100, 1 ≤ vb, vs ≤ 1000. The second line contains n non-negative integers in ascending order: coordinates xi of the bus stop with index i. It is guaranteed that x1 equals to zero, and xn ≤ 105. The third line contains the coordinates of the University, integers xu and yu, not exceeding 105 in absolute value.

## Output Format
In the only line output the answer to the problem — index of the optimum bus stop.

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

## Note
As you know, students are a special sort of people, and minibuses usually do not hurry. That's why you should not be surprised, if Student's speed is higher than the speed of the minibus.

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

# Problem
One beautiful July morning a terrible thing happened in Mainframe: a mean virus Megabyte somehow got access to the memory of his not less mean sister Hexadecimal. He loaded there a huge amount of n different natural numbers from 1 to n to obtain total control over her energy.

But his plan failed. The reason for this was very simple: Hexadecimal didn't perceive any information, apart from numbers written in binary format. This means that if a number in a decimal representation contained characters apart from 0 and 1, it was not stored in the memory. Now Megabyte wants to know, how many numbers were loaded successfully.

## Input Format
Input data contains the only number n (1 ≤ n ≤ 109).

## Output Format
Output the only number — answer to the problem.

## Examples
```input
10
```
```output
2
```

## Note
For n = 10 the answer includes numbers 1 and 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: 64.0 MB

# Problem
Hexadecimal likes drawing. She has drawn many graphs already, both directed and not. Recently she has started to work on a still-life «interesting graph and apples». An undirected graph is called interesting, if each of its vertices belongs to one cycle only — a funny ring — and does not belong to any other cycles. A funny ring is a cycle that goes through all the vertices just once. Moreover, loops are funny rings too.

She has already drawn the apples and some of the graph edges. But now it is not clear, how to connect the rest of the vertices to get an interesting graph as a result. The answer should contain the minimal amount of added edges. And furthermore, the answer should be the lexicographically smallest one. The set of edges (x1, y1), (x2, y2), ..., (xn, yn), where xi ≤ yi, is lexicographically smaller than the set (u1, v1), (u2, v2), ..., (un, vn), where ui ≤ vi, provided that the sequence of integers x1, y1, x2, y2, ..., xn, yn is lexicographically smaller than the sequence u1, v1, u2, v2, ..., un, vn. If you do not cope, Hexadecimal will eat you. ...eat you alive.

## Input Format
The first line of the input data contains a pair of integers n and m (1 ≤ n ≤ 50, 0 ≤ m ≤ 2500) — the amount of vertices and edges respectively. The following lines contain pairs of numbers xi and yi (1 ≤ xi, yi ≤ n) — the vertices that are already connected by edges. The initial graph may contain multiple edges and loops.

## Output Format
In the first line output «YES» or «NO»: if it is possible or not to construct an interesting graph. If the answer is «YES», in the second line output k — the amount of edges that should be added to the initial graph. Finally, output k lines: pairs of vertices xj and yj, between which edges should be drawn. The result may contain multiple edges and loops. k can be equal to zero.

## Examples
```input
3 2
1 2
2 3
```
```output
YES
1
1 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a connected undirected graph with n vertices and m edges. The vertices are enumerated from 1 to n.

You are given n integers c1, c2, ..., cn, each of them is between  - n and n, inclusive. It is also guaranteed that the parity of cv equals the parity of degree of vertex v. The degree of a vertex is the number of edges connected to it.

You are to write a weight between  - 2·n2 and 2·n2 (inclusive) on each edge in such a way, that for each vertex v the sum of weights on edges connected to this vertex is equal to cv, or determine that this is impossible.

## Input Format
The first line contains two integers n and m (2 ≤ n ≤ 105, n - 1 ≤ m ≤ 105) — the number of vertices and the number of edges.

The next line contains n integers c1, c2, ..., cn ( - n ≤ ci ≤ n), where ci is the required sum of weights of edges connected to vertex i. It is guaranteed that the parity of ci equals the parity of degree of vertex i.

The next m lines describe edges of the graph. The i-th of these lines contains two integers ai and bi (1 ≤ ai, bi ≤ n; ai ≠ bi), meaning that the i-th edge connects vertices ai and bi.

It is guaranteed that the given graph is connected and does not contain loops and multiple edges.

## Output Format
If there is no solution, print "NO".

Otherwise print "YES" and then m lines, the i-th of them is the weight of the i-th edge wi ( - 2·n2 ≤ wi ≤ 2·n2).

## Examples
```input
3 3
2 2 2
1 2
2 3
1 3
```
```output
YES
1
1
1
```
-----
```input
4 3
-1 0 2 1
1 2
2 3
3 4
```
```output
YES
-1
1
1
```
-----
```input
6 6
3 5 5 5 1 5
1 4
3 2
4 3
4 5
3 5
5 6
```
```output
YES
3
5
3
-1
-3
5
```
-----
```input
4 4
4 4 2 4
1 2
2 3
3 4
4 1
```
```output
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 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
We often go to supermarkets to buy some fruits or vegetables, and on the tag there prints the price for a kilo. But in some supermarkets, when asked how much the items are, the clerk will say that $$$a$$$ yuan for $$$b$$$ kilos (You don't need to care about what "yuan" is), the same as $$$a/b$$$ yuan for a kilo.

Now imagine you'd like to buy $$$m$$$ kilos of apples. You've asked $$$n$$$ supermarkets and got the prices. Find the minimum cost for those apples.

You can assume that there are enough apples in all supermarkets.

## Input Format
The first line contains two positive integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 5\,000$$$, $$$1 \leq m \leq 100$$$), denoting that there are $$$n$$$ supermarkets and you want to buy $$$m$$$ kilos of apples.

The following $$$n$$$ lines describe the information of the supermarkets. Each line contains two positive integers $$$a, b$$$ ($$$1 \leq a, b \leq 100$$$), denoting that in this supermarket, you are supposed to pay $$$a$$$ yuan for $$$b$$$ kilos of apples.

## Output Format
The only line, denoting the minimum cost for $$$m$$$ kilos of apples. Please make sure that the absolute or relative error between your answer and the correct answer won't exceed $$$10^{-6}$$$.

Formally, let your answer be $$$x$$$, and the jury's answer be $$$y$$$. Your answer is considered correct if $$$\frac{|x - y|}{\max{(1, |y|)}} \le 10^{-6}$$$.

## Examples
```input
3 5
1 2
3 4
1 3
```
```output
1.66666667
```
-----
```input
2 1
99 100
98 99
```
```output
0.98989899
```

## Note
In the first sample, you are supposed to buy $$$5$$$ kilos of apples in supermarket $$$3$$$. The cost is $$$5/3$$$ yuan.

In the second sample, you are supposed to buy $$$1$$$ kilo of apples in supermarket $$$2$$$. The cost is $$$98/99$$$ yuan.

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
We consider a positive integer perfect, if and only if the sum of its digits is exactly $$$10$$$. Given a positive integer $$$k$$$, your task is to find the $$$k$$$-th smallest perfect positive integer.

## Input Format
A single line with a positive integer $$$k$$$ ($$$1 \leq k \leq 10\,000$$$).

## Output Format
A single number, denoting the $$$k$$$-th smallest perfect integer.

## Examples
```input
1
```
```output
19
```
-----
```input
2
```
```output
28
```

## Note
The first perfect integer is $$$19$$$ and the second one is $$$28$$$.

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
Suppose that you are in a campus and have to go for classes day by day. As you may see, when you hurry to a classroom, you surprisingly find that many seats there are already occupied. Today you and your friends went for class, and found out that some of the seats were occupied.

The classroom contains $$$n$$$ rows of seats and there are $$$m$$$ seats in each row. Then the classroom can be represented as an $$$n \times m$$$ matrix. The character '.' represents an empty seat, while '*' means that the seat is occupied. You need to find $$$k$$$ consecutive empty seats in the same row or column and arrange those seats for you and your friends. Your task is to find the number of ways to arrange the seats. Two ways are considered different if sets of places that students occupy differs.

## Input Format
The first line contains three positive integers $$$n,m,k$$$ ($$$1 \leq n, m, k \leq 2\,000$$$), where $$$n,m$$$ represent the sizes of the classroom and $$$k$$$ is the number of consecutive seats you need to find.

Each of the next $$$n$$$ lines contains $$$m$$$ characters '.' or '*'. They form a matrix representing the classroom, '.' denotes an empty seat, and '*' denotes an occupied seat.

## Output Format
A single number, denoting the number of ways to find $$$k$$$ empty seats in the same row or column.

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

## Note
In the first sample, there are three ways to arrange those seats. You can take the following seats for your arrangement.

- $$$(1,3)$$$, $$$(2,3)$$$
- $$$(2,2)$$$, $$$(2,3)$$$
- $$$(2,1)$$$, $$$(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 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
Given an integer $$$x$$$. Your task is to find out how many positive integers $$$n$$$ ($$$1 \leq n \leq x$$$) satisfy $$$$$$n \cdot a^n \equiv b \quad (\textrm{mod}\;p),$$$$$$ where $$$a, b, p$$$ are all known constants.

## Input Format
The only line contains four integers $$$a,b,p,x$$$ ($$$2 \leq p \leq 10^6+3$$$, $$$1 \leq a,b < p$$$, $$$1 \leq x \leq 10^{12}$$$). It is guaranteed that $$$p$$$ is a prime.

## Output Format
Print a single integer: the number of possible answers $$$n$$$.

## Examples
```input
2 3 5 8
```
```output
2
```
-----
```input
4 6 7 13
```
```output
1
```
-----
```input
233 233 10007 1
```
```output
1
```

## Note
In the first sample, we can see that $$$n=2$$$ and $$$n=8$$$ are 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 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
There are n walruses sitting in a circle. All of them are numbered in the clockwise order: the walrus number 2 sits to the left of the walrus number 1, the walrus number 3 sits to the left of the walrus number 2, ..., the walrus number 1 sits to the left of the walrus number n.

The presenter has m chips. The presenter stands in the middle of the circle and starts giving the chips to the walruses starting from walrus number 1 and moving clockwise. The walrus number i gets i chips. If the presenter can't give the current walrus the required number of chips, then the presenter takes the remaining chips and the process ends. Determine by the given n and m how many chips the presenter will get in the end.

## Input Format
The first line contains two integers n and m (1 ≤ n ≤ 50, 1 ≤ m ≤ 104) — the number of walruses and the number of chips correspondingly.

## Output Format
Print the number of chips the presenter ended up with.

## Examples
```input
4 11
```
```output
0
```
-----
```input
17 107
```
```output
2
```
-----
```input
3 8
```
```output
1
```

## Note
In the first sample the presenter gives one chip to the walrus number 1, two chips to the walrus number 2, three chips to the walrus number 3, four chips to the walrus number 4, then again one chip to the walrus number 1. After that the presenter runs out of chips. He can't give anything to the walrus number 2 and the process finishes.

In the third sample the presenter gives one chip to the walrus number 1, two chips to the walrus number 2, three chips to the walrus number 3, then again one chip to the walrus number 1. The presenter has one chip left and he can't give two chips to the walrus number 2, that's why the presenter takes the last chip.

Now solve the problem and return the code.