vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Triskaidekaphobia is a fear of number 13. Ordinary people who suffer from this phobia feel uncomfortable around numbers 13, 130, 513 etc, but you, being a programmer, take this fear one step further. For example, consider number 7. It's ok when written in decimal, but written in base 4 it becomes 13, the dreadful number!

The more you think about it, the worse it looks. Number 100 has as many as 13 notations which contain 13! And there are numbers which have 13 in infinite number of their notations! Luckily, you can do any math in binary, which is completely safe from the nasty number. But still, you want to be able to estimate the level of nastiness of any number. 

Your task is: given an integer n, find the number of different integer bases b (b ≥ 2) for which n, written in base b, contains at least one 13. Assume that "digits" of the number in bases larger than 10 are written not as letters but as decimal numbers; thus, 30 in base 16 is not 1E but (1)(14) or simply 114. Please note, that 13 must be present as a substring of notation, not a subsequence (123 doesn't contain 13).

Input

The only line of the input contains a single integer n (1 ≤ n ≤ 105).

Output

Output a single integer — the number of different integer bases b (b ≥ 2) for which n, written in base b, contains at least one 13. If there are infinitely many such bases, output -1.

Examples

Input

7


Output

1


Input

100


Output

13


Input

13


Output

-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
DRM Encryption is a new kind of encryption. Given an encrypted string (which we’ll call a DRM message), the decryption process involves three steps: Divide, Rotate and Merge. This process is described in the following example with the DRM message “EWPGAJRB”:Divide

– First, divide the message in half to “EWPG” and “AJRB”.Rotate

– For each half, calculate its rotation value by summing up the values of each character ($\textrm{A} = 0, \textrm{B} = 1, \ldots , \textrm{Z} = 25$). The rotation value of “EWPG” is $4 + 22 + 15 + 6 = 47$. Rotate each character in “EWPG” $47$ positions forward (wrapping from Z to A when necessary) to obtain the new string “ZRKB”. Following the same process on “AJRB” results in “BKSC”.Merge

– The last step is to combine these new strings (“ZRKB” and “BKSC”) by rotating each character in the first string by the value of the corresponding character in the second string. For the first position, rotating ‘Z’ by ‘B’ means moving it forward 1 character, which wraps it around to ‘A’. Continuing this process for every character results in the final decrypted message, “ABCD”.

-----Input-----
The input contains a single DRM message to be decrypted. All characters in the string are uppercase letters and the string’s length is even and $\leq 15000$.

-----Output-----
Display the decrypted DRM message.

-----Examples-----
Sample Input:
EWPGAJRB
Sample Output:
ABCD

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ahoy Matey!

Welcome to the seven seas.

You are the captain of a pirate ship.

You are in battle against the royal navy.

You have cannons at the ready.... or are they?

Your task is to check if the gunners are loaded and ready, if they are: ```Fire!```

If they aren't ready: ```Shiver me timbers!```

Your gunners for each test case are 4 or less.

When you check if they are ready their answers are in a dictionary and will either be: ```aye``` or ```nay```

Firing with less than all gunners ready is non-optimum (this is not fire at will, this is fire by the captain's orders or walk the plank, dirty sea-dog!)

If all answers are 'aye' then Fire!
if one or more are 'nay' then Shiver me timbers!

Also, check out the new Pirates!! Kata:
https://www.codewars.com/kata/57e2d5f473aa6a476b0000fe

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Sonya and Problem Wihtout a Legend

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Sonya was unable to think of a story for this problem, so here comes the formal description.

You are given the array containing *n* positive integers. At one turn you can pick any element and increase or decrease it by 1. The goal is the make the array strictly increasing by making the minimum possible number of operations. You are allowed to change elements in any way, they can become negative or equal to 0.

Input Specification:
The first line of the input contains a single integer *n* (1<=≤<=*n*<=≤<=3000) — the length of the array.

Next line contains *n* integer *a**i* (1<=≤<=*a**i*<=≤<=109).

Output Specification:
Print the minimum number of operation required to make the array strictly increasing.

Demo Input:
['7\n2 1 5 11 5 9 11\n', '5\n5 4 3 2 1\n']

Demo Output:
['9\n', '12\n']

Note:
In the first sample, the array is going to look as follows:

2 3 5 6 7 9 11

|2 - 2| + |1 - 3| + |5 - 5| + |11 - 6| + |5 - 7| + |9 - 9| + |11 - 11| = 9

And for the second sample:

1 2 3 4 5

|5 - 1| + |4 - 2| + |3 - 3| + |2 - 4| + |1 - 5| = 12

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In a distributed system, data is never where you need it, and fetching data over a network takes time and consumes bandwidth. The problem can be mitigated by adding a cache, where a node stores some resources locally and if those resources need to be used again, it can simply take them from its cache rather than asking someone else for them. 

However, caches have a nasty tendency to fill up, so at some point, objects must be evicted from the cache to make room for new objects. Choosing what object to remove from the cache is not easy and there are several different algorithms to choose from.

The marvelous Apes in Computing Machinery have come up with a fantastic new algorithm, the Introspective Caching Algorithm, named after a city of Peru. It consists of some extra hardware (a very small, precognitive monkey) which helps making decisions. Since the monkey can see into the future, she knows exactly what objects will be accessed and in what order, and using this information she will make optimal decisions on what objects to remove from the cache. Optimality here means that she will minimize the number of times an object is read into the cache.

All object accesses go through the cache, so every time an object is accessed, it must be inserted into the cache if it was not already there. All objects are of equal size, and no writes occur in the system, so a cached object is always valid. When the system starts, the cache is empty.

You have been tasked with evaluating the monkey’s performance, and feeding her the occasional banana.

-----Input-----
The first line of input contains three integers, separated by single spaces, telling you how many objects fit in the cache, $0 < c \le 10000$, how many different objects are in the system, $c \le n \le 100000$, and how many accesses, $0 \le a \le 100000$, will occur. The following $a$ lines contain a single integer between $0$ and $n-1$ (inclusive) indicating what object is accessed. The first line corresponds to the first object accessed access and the last line to the last.

-----Output-----
Output the least number of times an object must be read into the cache to handle the accesses listed in the input.

-----Examples-----
Sample Input:
1 2 3
0
0
1
Sample Output:
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Maksim walks on a Cartesian plane. Initially, he stands at the point $(0, 0)$ and in one move he can go to any of four adjacent points (left, right, up, down). For example, if Maksim is currently at the point $(0, 0)$, he can go to any of the following points in one move:   $(1, 0)$;  $(0, 1)$;  $(-1, 0)$;  $(0, -1)$. 

There are also $n$ distinct key points at this plane. The $i$-th point is $p_i = (x_i, y_i)$. It is guaranteed that $0 \le x_i$ and $0 \le y_i$ and there is no key point $(0, 0)$.

Let the first level points be such points that $max(x_i, y_i) = 1$, the second level points be such points that $max(x_i, y_i) = 2$ and so on. Maksim wants to visit all the key points. But he shouldn't visit points of level $i + 1$ if he does not visit all the points of level $i$. He starts visiting the points from the minimum level of point from the given set.

The distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is $|x_1 - x_2| + |y_1 - y_2|$ where $|v|$ is the absolute value of $v$.

Maksim wants to visit all the key points in such a way that the total distance he walks will be minimum possible. Your task is to find this distance.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of key points.

Each of the next $n$ lines contains two integers $x_i$, $y_i$ ($0 \le x_i, y_i \le 10^9$) — $x$-coordinate of the key point $p_i$ and $y$-coordinate of the key point $p_i$. It is guaranteed that all the points are distinct and the point $(0, 0)$ is not in this set.


-----Output-----

Print one integer — the minimum possible total distance Maksim has to travel if he needs to visit all key points in a way described above.


-----Examples-----
Input
8
2 2
1 4
2 3
3 1
3 4
1 1
4 3
1 2

Output
15

Input
5
2 1
1 0
2 0
3 2
0 3

Output
9



-----Note-----

The picture corresponding to the first example: [Image]

There is one of the possible answers of length $15$.

The picture corresponding to the second example: [Image]

There is one of the possible answers of length $9$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Limak has a string S, that consists of N lowercase English letters.
Limak then created a new string by repeating S exactly K times.
For example, for S = "abcb" and K = 2, he would get "abcbabcb".
Your task is to count the number of subsequences "ab" (not necessarily consecutive) in the new string.
In other words, find the number pairs of indices i < j, such that the i-th and j-th characters in the new string are 'a' and 'b' respectively.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two integers N and K, denoting the length of the initial string S and the number of repetitions respectively.
The second line contains a string S.
Its length is exactly N, and each of its characters is a lowercase English letter.

-----Output-----
For each test case, output a single line containing one integer — the number of subsequences "ab" in the new string.
For the given constraints, it can be proved that the answer fits in the 64-bit signed type.

-----Constraints-----
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 105
- 1 ≤ N * K ≤ 109 (in other words, the new string has length up to 109)

-----Example-----
Input:
3
4 2
abcb
7 1
aayzbaa
12 80123123
abzbabzbazab

Output:
6
2
64197148392731290

-----Explanation-----
Test case 1. Limak repeated the string "abcb" 2 times, and so he got "abcbabcb". There are 6 occurrences of the subsequence "ab":
- ABcbabcb (the two letters marked uppercase)
- AbcBabcb
- AbcbaBcb
- AbcbabcB
- abcbABcb
- abcbAbcB
Test case 2. Since K = 1, the new string is equal to the given S ("aayzbaa"). There are 2 occurrences of the subsequence "ab" in this string: AayzBaa and aAyzBaa.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
New Year is coming in Line World! In this world, there are n cells numbered by integers from 1 to n, as a 1 × n board. People live in cells. However, it was hard to move between distinct cells, because of the difficulty of escaping the cell. People wanted to meet people who live in other cells.

So, user tncks0121 has made a transportation system to move between these cells, to celebrate the New Year. First, he thought of n - 1 positive integers a_1, a_2, ..., a_{n} - 1. For every integer i where 1 ≤ i ≤ n - 1 the condition 1 ≤ a_{i} ≤ n - i holds. Next, he made n - 1 portals, numbered by integers from 1 to n - 1. The i-th (1 ≤ i ≤ n - 1) portal connects cell i and cell (i + a_{i}), and one can travel from cell i to cell (i + a_{i}) using the i-th portal. Unfortunately, one cannot use the portal backwards, which means one cannot move from cell (i + a_{i}) to cell i using the i-th portal. It is easy to see that because of condition 1 ≤ a_{i} ≤ n - i one can't leave the Line World using portals.

Currently, I am standing at cell 1, and I want to go to cell t. However, I don't know whether it is possible to go there. Please determine whether I can go to cell t by only using the construted transportation system.


-----Input-----

The first line contains two space-separated integers n (3 ≤ n ≤ 3 × 10^4) and t (2 ≤ t ≤ n) — the number of cells, and the index of the cell which I want to go to.

The second line contains n - 1 space-separated integers a_1, a_2, ..., a_{n} - 1 (1 ≤ a_{i} ≤ n - i). It is guaranteed, that using the given transportation system, one cannot leave the Line World.


-----Output-----

If I can go to cell t using the transportation system, print "YES". Otherwise, print "NO".


-----Examples-----
Input
8 4
1 2 1 2 1 2 1

Output
YES

Input
8 5
1 2 1 2 1 1 1

Output
NO



-----Note-----

In the first sample, the visited cells are: 1, 2, 4; so we can successfully visit the cell 4.

In the second sample, the possible cells to visit are: 1, 2, 4, 6, 7, 8; so we can't visit the cell 5, which we want to visit.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp was given a row of tiles. Each tile contains one lowercase letter of the Latin alphabet. The entire sequence of tiles forms the string $s$.

In other words, you are given a string $s$ consisting of lowercase Latin letters.

Initially, Polycarp is on the first tile of the row and wants to get to the last tile by jumping on the tiles. Jumping from $i$-th tile to $j$-th tile has a cost equal to $|index(s_i) - index(s_j)|$, where $index(c)$ is the index of the letter $c$ in the alphabet (for example, $index($'a'$)=1$, $index($'b'$)=2$, ..., $index($'z'$)=26$) .

Polycarp wants to get to the $n$-th tile for the minimum total cost, but at the same time make maximum number of jumps.

In other words, among all possible ways to get to the last tile for the minimum total cost, he will choose the one with the maximum number of jumps.

Polycarp can visit each tile at most once.

Polycarp asks you to help — print the sequence of indices of string $s$ on which he should jump.


-----Input-----

The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test.

Each test case is given by the string $s$ ($2 \le |s| \le 2 \cdot 10^5$), where $|s|$ — is the length of string $s$. The string $s$ consists of lowercase Latin letters.

It is guaranteed that the sum of string lengths $s$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

The answer to each test case consists of two lines.

In the first line print two integers $cost$, $m$, where $cost$ is the minimum total cost of the path, and $m$ is the maximum number of visited tiles Polycarp can make to get to $n$-th tiles for the minimum total cost $cost$ (i.e. the number of jumps is $m-1$).

In the next line print $m$ different numbers $j_1, j_2, \dots, j_m$ ($1 \le j_i \le |s|$) — the sequence of indices of the tiles Polycarp will jump on. The first number in the sequence must be $1$ (that is, $j_1=1$) and the last number must be the value of $|s|$ (that is, $j_m=|s|$).

If there are multiple answers, print any of them.


-----Examples-----

Input
6
logic
codeforces
bca
aaaaaaaaaaa
adbaadabad
to
Output
9 4
1 4 3 5
16 10
1 8 3 4 9 5 2 6 7 10
1 2
1 3
0 11
1 8 10 4 3 5 7 2 9 6 11
3 10
1 9 5 4 7 3 8 6 2 10
5 2
1 2


-----Note-----

In the first test case, the required path corresponds to the picture:

In this case, the minimum possible total cost of the path is achieved. Since $index($'l'$)=12$, $index($'o'$)=15$, $index($'g'$)=7$, $index($'i'$)=9$, $index($'c'$)=3$, then the total cost of the path is $|12-9|+|9-7|+|7-3|=3+2+4=9$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Order Book

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
In this task you need to process a set of stock exchange orders and use them to create order book.

An order is an instruction of some participant to buy or sell stocks on stock exchange. The order number *i* has price *p**i*, direction *d**i* — buy or sell, and integer *q**i*. This means that the participant is ready to buy or sell *q**i* stocks at price *p**i* for one stock. A value *q**i* is also known as a volume of an order.

All orders with the same price *p* and direction *d* are merged into one aggregated order with price *p* and direction *d*. The volume of such order is a sum of volumes of the initial orders.

An order book is a list of aggregated orders, the first part of which contains sell orders sorted by price in descending order, the second contains buy orders also sorted by price in descending order.

An order book of depth *s* contains *s* best aggregated orders for each direction. A buy order is better if it has higher price and a sell order is better if it has lower price. If there are less than *s* aggregated orders for some direction then all of them will be in the final order book.

You are given *n* stock exhange orders. Your task is to print order book of depth *s* for these orders.

Input Specification:
The input starts with two positive integers *n* and *s* (1<=≤<=*n*<=≤<=1000,<=1<=≤<=*s*<=≤<=50), the number of orders and the book depth.

Next *n* lines contains a letter *d**i* (either 'B' or 'S'), an integer *p**i* (0<=≤<=*p**i*<=≤<=105) and an integer *q**i* (1<=≤<=*q**i*<=≤<=104) — direction, price and volume respectively. The letter 'B' means buy, 'S' means sell. The price of any sell order is higher than the price of any buy order.

Output Specification:
Print no more than 2*s* lines with aggregated orders from order book of depth *s*. The output format for orders should be the same as in input.

Demo Input:
['6 2\nB 10 3\nS 50 2\nS 40 1\nS 50 6\nB 20 4\nB 25 10\n']

Demo Output:
['S 50 8\nS 40 1\nB 25 10\nB 20 4\n']

Note:
Denote (x, y) an order with price *x* and volume *y*. There are 3 aggregated buy orders (10, 3), (20, 4), (25, 10) and two sell orders (50, 8), (40, 1) in the sample.

You need to print no more than two best orders for each direction, so you shouldn't print the order (10 3) having the worst price among buy orders.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a quadratic equation with integer coefficients A * X2 + B * X + C = 0. It is guaranteed that A ≠ 0 and that the equation has at least one real root. Output the roots of the equation.

Input

The only line of input contains integers A, B and C ( - 1000 ≤ A, B, C ≤ 1000, A ≠ 0), separated by spaces.

Output

Output the roots of the equation in increasing order. If the equation has a single root of multiplicity 2, output it once. The root is considered to be correct if its absolute or relative error does not exceed 10 - 4.

Examples

Input

1 -2 1


Output

1


Input

1 0 -1


Output

-1 1


Input

2 -3 1


Output

0.5 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the NN country, there are n cities, numbered from 1 to n, and n - 1 roads, connecting them. There is a roads path between any two cities.

There are m bidirectional bus routes between cities. Buses drive between two cities taking the shortest path with stops in every city they drive through. Travelling by bus, you can travel from any stop on the route to any other. You can travel between cities only by bus.

You are interested in q questions: is it possible to get from one city to another and what is the minimum number of buses you need to use for it?

Input

The first line contains a single integer n (2 ≤ n ≤ 2 ⋅ 10^5) — the number of cities.

The second line contains n - 1 integers p_2, p_3, …, p_n (1 ≤ p_i < i), where p_i means that cities p_i and i are connected by road.

The third line contains a single integer m (1 ≤ m ≤ 2 ⋅ 10^5) — the number of bus routes.

Each of the next m lines contains 2 integers a and b (1 ≤ a, b ≤ n, a ≠ b), meaning that there is a bus route between cities a and b. It is possible that there is more than one route between two cities.

The next line contains a single integer q (1 ≤ q ≤ 2 ⋅ 10^5) — the number of questions you are interested in.

Each of the next q lines contains 2 integers v and u (1 ≤ v, u ≤ n, v ≠ u), meaning that you are interested if it is possible to get from city v to city u and what is the minimum number of buses you need to use for it.

Output

Print the answer for each question on a separate line. If there is no way to get from one city to another, print -1. Otherwise print the minimum number of buses you have to use.

Examples

Input

7
1 1 1 4 5 6
4
4 2
5 4
1 3
6 7
6
4 5
3 5
7 2
4 5
3 2
5 3


Output

1
3
-1
1
2
3


Input

7
1 1 2 3 4 1
4
4 7
3 5
7 6
7 6
6
4 6
3 1
3 2
2 7
6 3
5 3


Output

1
-1
-1
1
-1
1

Note

<image> Routes for first sample are marked on the picture. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
She is an apprentice wizard. She first learned the magic of manipulating time. And she decided to open a liquor store to earn a living. It has to do with the fact that all the inhabitants of the country where she lives love alcohol. Residents especially like sake that has been aged for many years, and its value increases proportionally with the number of years it has been aged. It's easy to imagine that 100-year-old liquor is more valuable than 50-year-old liquor. And it's also difficult to get. She used her magic to instantly make a long-aged liquor and sell it to earn money.

She priced the sake according to the number of years it was aged. For example, if you need 5 years of aging, you will have to pay 5 emers, and if you have 100 years of aging, you will have to pay 100 emers. For her, making either one uses the same magic, so there is no difference. A long-term aging order is better for her.

Since she is still immature, there are two restrictions on the magic that can be used now. She can't age sake for more than n years now. Also, there are m integers, and it is impossible for her to age sake for those and multiple years.

She is worried if she can live only by running a liquor store. She cannot predict how much income she will earn. So I decided to decide if I needed to do another job based on my expected daily income. Fortunately, she can grow vegetables, take care of pets, cook, sew, carpentry, and so on, so even if she has a small income at a liquor store, she doesn't seem to be in trouble.

It's your job to calculate the expected value of her daily income. The following three may be assumed when calculating the expected value.


Only one order can be accepted per day.
Residents do not order liquor for years that she cannot make.
The number of years of inhabitants' orders is evenly distributed.




Input

The input consists of multiple cases. Each case is given in the following format.


n m
p0 ... pm-1


Residents request liquor that has been aged for the number of years with an integer value between 1 and n.
However, no one asks for m integer pi and its multiples.

The end of the input is given with n = 0 and m = 0.

Each value meets the following conditions
2 ≤ n ≤ 2,000,000,000
1 ≤ m ≤ 20
Also, pi is guaranteed to be divisible by n.


The number of test cases does not exceed 200.

Output

Output the expected value of her daily income.
If there is no possible number of years for the resident's order, output 0 as the expected value of the answer.


The correct answer prepared by the judge and an error of 1e-5 or less are allowed as the correct answer.

Example

Input

12 3
2 3 6
12 4
1 2 3 6
0 0


Output

6.0000000000
0.0000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.