vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Maj loves pickled cucumber (also known as pickles). However, her partner is not as keen on filling a sandwich with pickles. Maj would like to maximize the amount of pickles on a sandwich, while still avoiding being judged by her partner. 

Both Maj’s sandwich and the pickles have a circular shape. The sandwich has radius $s$ cm and the pickles have radius $r$ cm.

Maj has exactly $n$ pickles. She wants to place as many of them as possible on her sandwich, as long as:
 - at most $z \% $ of the area of the sandwich is covered by pickles.
 - no two pickles overlap (but they are allowed to touch).

How many pickles can Maj place on her sandwich?

-----Input-----
The input consists of:
 - one line with the decimal numbers $s$ and $r$ ($1 \le s \le 10$, $0.5 \le r \le s$, at most $6$ digits after the decimal point), the radius of the sandwich and the radius of a pickle, in centimetres.
 - one line with the integers $n$ and $z$ ($1 \le n \le 7$, $0 \le z \le 100$), the number of pickles Maj have, and the maximum area she may cover with them, in percent.

-----Output-----
Output the maximum number of pickles Maj can place on her sandwich. The input will always be constructed such that this number does not change if the radius of the sandwich increases or decreases by $10^{-6}$.

-----Examples-----
Sample Input:
3 1 4 40
Sample Output:
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bash has set out on a journey to become the greatest Pokemon master. To get his first Pokemon, he went to Professor Zulu's Lab. Since Bash is Professor Zulu's favourite student, Zulu allows him to take as many Pokemon from his lab as he pleases.

But Zulu warns him that a group of k > 1 Pokemon with strengths {s_1, s_2, s_3, ..., s_{k}} tend to fight among each other if gcd(s_1, s_2, s_3, ..., s_{k}) = 1 (see notes for gcd definition).

Bash, being smart, does not want his Pokemon to fight among each other. However, he also wants to maximize the number of Pokemon he takes from the lab. Can you help Bash find out the maximum number of Pokemon he can take? 

Note: A Pokemon cannot fight with itself.


-----Input-----

The input consists of two lines.

The first line contains an integer n (1 ≤ n ≤ 10^5), the number of Pokemon in the lab.

The next line contains n space separated integers, where the i-th of them denotes s_{i} (1 ≤ s_{i} ≤ 10^5), the strength of the i-th Pokemon.


-----Output-----

Print single integer — the maximum number of Pokemons Bash can take.


-----Examples-----
Input
3
2 3 4

Output
2

Input
5
2 3 4 6 7

Output
3



-----Note-----

gcd (greatest common divisor) of positive integers set {a_1, a_2, ..., a_{n}} is the maximum positive integer that divides all the integers {a_1, a_2, ..., a_{n}}.

In the first sample, we can take Pokemons with strengths {2, 4} since gcd(2, 4) = 2.

In the second sample, we can take Pokemons with strengths {2, 4, 6}, and there is no larger group with gcd ≠ 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has two distinct positive integers A and B. 

Chef wonders how many distinct values are possible for the expression \mathrm{gcd}(A+X,B+X), where X can take any non-negative integer value.

Help Chef find this value.

Here, \mathrm{gcd} stands for [Greatest Common Divisor].

------ Input Format ------ 

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first and only line of each test case contains two distinct space separated integers A and B.

------ Output Format ------ 

For each testcase, output the number of distinct values of the expression \mathrm{gcd}(A+X,B+X), where X can take any non-negative integer value.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ A, B ≤ 10^{9}$
$A \neq B$

----- Sample Input 1 ------ 
2
1 2
12 8

----- Sample Output 1 ------ 
1
3

----- explanation 1 ------ 
Test case 1: Here $\mathrm{gcd}(1+X, 2+X) = 1$ no matter what value of $X$ you choose.

Test case 2: 
- If we take $X = 0$, $\mathrm{gcd}(12, 8) = 4$.
- If we take $X = 1$, $\mathrm{gcd}(13, 9) = 1$.
- If we take $X = 2$, $\mathrm{gcd}(14, 10) = 2$.

It can be shown that no other value of $\mathrm{gcd}$ is possible.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Kyoya and Permutation

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Let's define the permutation of length *n* as an array *p*<==<=[*p*1,<=*p*2,<=...,<=*p**n*] consisting of *n* distinct integers from range from 1 to *n*. We say that this permutation maps value 1 into the value *p*1, value 2 into the value *p*2 and so on.

Kyota Ootori has just learned about cyclic representation of a permutation. A cycle is a sequence of numbers such that each element of this sequence is being mapped into the next element of this sequence (and the last element of the cycle is being mapped into the first element of the cycle). The cyclic representation is a representation of *p* as a collection of cycles forming *p*. For example, permutation *p*<==<=[4,<=1,<=6,<=2,<=5,<=3] has a cyclic representation that looks like (142)(36)(5) because 1 is replaced by 4, 4 is replaced by 2, 2 is replaced by 1, 3 and 6 are swapped, and 5 remains in place. 

Permutation may have several cyclic representations, so Kyoya defines the standard cyclic representation of a permutation as follows. First, reorder the elements within each cycle so the largest element is first. Then, reorder all of the cycles so they are sorted by their first element. For our example above, the standard cyclic representation of [4,<=1,<=6,<=2,<=5,<=3] is (421)(5)(63).

Now, Kyoya notices that if we drop the parenthesis in the standard cyclic representation, we get another permutation! For instance, [4,<=1,<=6,<=2,<=5,<=3] will become [4,<=2,<=1,<=5,<=6,<=3].

Kyoya notices that some permutations don't change after applying operation described above at all. He wrote all permutations of length *n* that do not change in a list in lexicographic order. Unfortunately, his friend Tamaki Suoh lost this list. Kyoya wishes to reproduce the list and he needs your help. Given the integers *n* and *k*, print the permutation that was *k*-th on Kyoya's list.

Input Specification:
The first line will contain two integers *n*, *k* (1<=≤<=*n*<=≤<=50, 1<=≤<=*k*<=≤<=*min*{1018,<=*l*} where *l* is the length of the Kyoya's list).

Output Specification:
Print *n* space-separated integers, representing the permutation that is the answer for the question.

Demo Input:
['4 3\n', '10 1\n']

Demo Output:
['1 3 2 4\n', '1 2 3 4 5 6 7 8 9 10\n']

Note:
The standard cycle representation is (1)(32)(4), which after removing parenthesis gives us the original permutation. The first permutation on the list would be [1, 2, 3, 4], while the second permutation would be [1, 2, 4, 3].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
"Perket" is a widely known and delicious meal. For perket to be what it is, cooks must carefully choose the ingredients to get the fullest taste possible while keeping the meal traditional.

You have $N$ ingredients at your disposal. For each we know its sourness $S$ and bitterness $B$. When using multiple ingredients, the total sourness is the product of sourness amounts of all ingredients, while the total bitterness is the sum of bitterness amounts of all ingredients.

As everyone knows, perket is supposed to be neither sour nor bitter; we want to choose the ingredients so that the absolute difference between sourness and bitterness is the smallest.

Also, it is necessary to use at least one ingredient; you can’t serve water as the main course.

-----Input-----
The first line contains the integer $N$ $(1 \leq N \leq 10)$, the number of ingredients at our disposal. Each of the next $N$ lines contains two integers separated by a space, the sourness and bitterness of each ingredient.

The input data will be such that, if we make a meal with all ingredients, both the sourness and bitterness will be less than $1000000000$.

-----Output-----
Output the smallest possible difference between sourness and bitterness.

-----Examples-----
Sample Input 1:
1
3 10
Sample Output 1:
7

Sample Input 2:
2
3 8
5 8
Sample Output 2:
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently a Golden Circle of Beetlovers was found in Byteland. It is a circle route going through n ⋅ k cities. The cities are numerated from 1 to n ⋅ k, the distance between the neighboring cities is exactly 1 km.

Sergey does not like beetles, he loves burgers. Fortunately for him, there are n fast food restaurants on the circle, they are located in the 1-st, the (k + 1)-st, the (2k + 1)-st, and so on, the ((n-1)k + 1)-st cities, i.e. the distance between the neighboring cities with fast food restaurants is k km.

Sergey began his journey at some city s and traveled along the circle, making stops at cities each l km (l > 0), until he stopped in s once again. Sergey then forgot numbers s and l, but he remembers that the distance from the city s to the nearest fast food restaurant was a km, and the distance from the city he stopped at after traveling the first l km from s to the nearest fast food restaurant was b km. Sergey always traveled in the same direction along the circle, but when he calculated distances to the restaurants, he considered both directions.

Now Sergey is interested in two integers. The first integer x is the minimum number of stops (excluding the first) Sergey could have done before returning to s. The second integer y is the maximum number of stops (excluding the first) Sergey could have done before returning to s.

Input

The first line contains two integers n and k (1 ≤ n, k ≤ 100 000) — the number of fast food restaurants on the circle and the distance between the neighboring restaurants, respectively.

The second line contains two integers a and b (0 ≤ a, b ≤ k/2) — the distances to the nearest fast food restaurants from the initial city and from the city Sergey made the first stop at, respectively.

Output

Print the two integers x and y.

Examples

Input


2 3
1 1


Output


1 6


Input


3 2
0 0


Output


1 3


Input


1 10
5 3


Output


5 5

Note

In the first example the restaurants are located in the cities 1 and 4, the initial city s could be 2, 3, 5, or 6. The next city Sergey stopped at could also be at cities 2, 3, 5, 6. Let's loop through all possible combinations of these cities. If both s and the city of the first stop are at the city 2 (for example, l = 6), then Sergey is at s after the first stop already, so x = 1. In other pairs Sergey needs 1, 2, 3, or 6 stops to return to s, so y = 6.

In the second example Sergey was at cities with fast food restaurant both initially and after the first stop, so l is 2, 4, or 6. Thus x = 1, y = 3.

In the third example there is only one restaurant, so the possible locations of s and the first stop are: (6, 8) and (6, 4). For the first option l = 2, for the second l = 8. In both cases Sergey needs x=y=5 stops to go to s.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Protection of the Indian border and safe transport of items from one point to another along the border are the paramount jobs for the Indian army. However they need some information about the protection status along the length of the border. The border can be viewed as the real x-axis. Along the axis, Indian army has N checkpoints for lookout. 
We know that each checkpoint is located at an integer location xi. Each checkpoint must have a fleet of armed men which are responsible for guarding the neighboring areas of the checkpoint and provide military assistance of all kinds. The size of the fleet is based on the location of the checkpoint and how active the region is for terrorist activities.

Given the number of armed men assigned at the i^th checkpoint, as pi, this information is available for all checkpoints. 
With the skills of the armed men, it is known that if for the i^th checkpoint, the length on the x axis that they can defend is a closed interval [xi-pi, xi+pi].
Now, your task is to transport some military items from position S to the end position E on the x-axis.
Input:
First line of the input contains 3 integers N, S and E. N is the number of checkpoints that the Indian Army has on the border.
Then N lines follow. i^th line contains 2 integers, xi and pi.

Output:
Print the total distance of the x-axisfrom S to E, that is not protected by the armed forces.

Constraints:
1 ≤ N ≤ 10^5
1 ≤ xi, pi ≤ 10^18
xi + pi ≤ 10^18
1 ≤ S ≤ E ≤ 10^18

SAMPLE INPUT
5 229 8419
1795 95
4873 720
3149 81
6101 2325
3674 629

SAMPLE OUTPUT
2626

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently Vasya decided to improve his pistol shooting skills. Today his coach offered him the following exercise. He placed n cans in a row on a table. Cans are numbered from left to right from 1 to n. Vasya has to knock down each can exactly once to finish the exercise. He is allowed to choose the order in which he will knock the cans down.

Vasya knows that the durability of the i-th can is a_i. It means that if Vasya has already knocked x cans down and is now about to start shooting the i-th one, he will need (a_i ⋅ x + 1) shots to knock it down. You can assume that if Vasya starts shooting the i-th can, he will be shooting it until he knocks it down.

Your task is to choose such an order of shooting so that the number of shots required to knock each of the n given cans down exactly once is minimum possible.

Input

The first line of the input contains one integer n (2 ≤ n ≤ 1 000) — the number of cans.

The second line of the input contains the sequence a_1, a_2, ..., a_n (1 ≤ a_i ≤ 1 000), where a_i is the durability of the i-th can.

Output

In the first line print the minimum number of shots required to knock each of the n given cans down exactly once.

In the second line print the sequence consisting of n distinct integers from 1 to n — the order of indices of cans that minimizes the number of shots required. If there are several answers, you can print any of them.

Examples

Input


3
20 10 20


Output


43
1 3 2 


Input


4
10 10 10 10


Output


64
2 1 4 3 


Input


6
5 4 5 4 4 5


Output


69
6 1 3 5 2 4 


Input


2
1 4


Output


3
2 1 

Note

In the first example Vasya can start shooting from the first can. He knocks it down with the first shot because he haven't knocked any other cans down before. After that he has to shoot the third can. To knock it down he shoots 20 ⋅ 1 + 1 = 21 times. After that only second can remains. To knock it down Vasya shoots 10 ⋅ 2 + 1 = 21 times. So the total number of shots is 1 + 21 + 21 = 43.

In the second example the order of shooting does not matter because all cans have the same durability.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Find the second-to-last element of a list.

Example:
```python
penultimate([1,2,3,4])            # => 3
penultimate(["Python is dynamic"]) # => 'i'
(courtesy of [haskell.org](http://www.haskell.org/haskellwiki/99_questions/1_to_10))
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are many excellent strategy board games, and your favourite among them is called “Steel Age”. It offers many different paths to victory but you prefer the blood-and-fire-strategy: build as many soldiers as possible and club your opposition into submission. To be able to build soldiers you need two resources: iron ore and coal. 

The board consists of different cells numbered from $1$ to $n$ which can contain resources. The rules for moving from one cell to another are rather complicated: if you can move from cell A to cell B, it does not always mean that you can also move from B to A. For example, if two cells are connected by a river, then you may be able to move downstream, but not upstream, so long as you didn’t invent a steam engine; however, it still could be possible to reach the upstream cell by using roads and taking a detour over other cells.

At the beginning of the game you own only one such cell, where all your settlers are located. At every move you are allowed to move an arbitrary number of settlers from a cell to one of its accessible neighbours. By moving your settlers into a cell for the first time, you “claim” it. Every claimed cell will bind one settler, which has to stay in this cell until the end of the game. However, there is no need to leave a settler in your initial cell because it is where your palace is located and thus the cell stays claimed for all time.

Your goal is to claim at least one cell containing the resource “iron ore” and at least one cell with resource “coal” in order to be able to build soldiers. What is the minimal number of settlers you need to reach this goal?

-----Input-----
The input consists of:
 - One line with three integers $n$ ($2 \le n \le 10^5$), the number of cells on the playing field, $m$ ($1 \le m < n$), the number of cells containing iron ore, and $k$ ($1 \le k < n$), the number of cells containing coal.
 - One line with $m$ distinct integers $o_1, \ldots , o_ m$ ($1 \le o_ i \le n$ for all $1\le i\le m$), where $o_1, \ldots , o_ m$ are the IDs of cells with iron ore.
 - One line with $k$ distinct integers $c_1, \ldots , c_ k$ ($1 \le c_ i \le n$ for all $1\le i\le k$), where $c_1, \ldots , c_ k$ are the IDs of cells with coal.
 - $n$ lines describing the topology of the board. The $j$-th line of this block specifies the accessible neighbours of the $j$-th cell and consists of the following integers:
 - One integer $0\le a \le 10$, the number of cells accessible from cell $j$.
 - $a$ distinct integers $b_1,\dots , b_ a$ ($1 \le b_ i \le n$, $b_ i \ne j$ for all $1\le i\le a$), the IDs of the cells accessible from cell $j$.

It is guaranteed, that no cell contains both resources, iron ore and coal. At the beginning of the game you own only the cell with ID $1$.

-----Output-----
Output the minimum number of settlers needed to claim at least one cell with coal and at least one cell with iron ore. Output “impossible” if it is impossible to own both, coal and iron ore.

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
*Mario has reached Bowser's Castle and is inches away from rescuing Princess Peach. He has to answer the following problem at the gate to be allowed to enter. Can you help him?*

Let S(M) denote the set of all [prime] [factors] of M.  
Given two positive integers A and B, determine whether A is divisible by all elements in S(B).

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of a single line of input, A and B, as mentioned in the statement.

------ Output Format ------ 

For each test case, print YES if A is divisible by all elements in S(B) and NO otherwise. 

You may print each character of the string in uppercase or lowercase (for example, the strings YES, yEs, yes, and yeS will all be treated as identical).

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ A, B ≤ 10^{18}$

----- Sample Input 1 ------ 
3
21 63
72 72
25 20
----- Sample Output 1 ------ 
YES
YES
NO
----- explanation 1 ------ 
Test case $1$: The set of all prime factors of $B = 63$ is given by $S(B) = \{3, 7\}$. Also, $A = 21$ is divisible by all elements in $S(B)$.

Test case $2$: The set of all prime factors of $B = 72$ is given by $S(B) = \{2, 3\}$. Also, $A = 72$ is divisible by all elements in $S(B)$.

Test case $3$: The set of all prime factors of $B = 20$ is given by $S(B) = \{2, 5\}$. Here, $A = 25$ is not divisible by $2$ in $S(B)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice's hair is growing by leaps and bounds. Maybe the cause of it is the excess of vitamins, or maybe it is some black magic...

To prevent this, Alice decided to go to the hairdresser. She wants for her hair length to be at most l centimeters after haircut, where l is her favorite number. Suppose, that the Alice's head is a straight line on which n hairlines grow. Let's number them from 1 to n. With one swing of the scissors the hairdresser can shorten all hairlines on any segment to the length l, given that all hairlines on that segment had length strictly greater than l. The hairdresser wants to complete his job as fast as possible, so he will make the least possible number of swings of scissors, since each swing of scissors takes one second.

Alice hasn't decided yet when she would go to the hairdresser, so she asked you to calculate how much time the haircut would take depending on the time she would go to the hairdresser. In particular, you need to process queries of two types:

  * 0 — Alice asks how much time the haircut would take if she would go to the hairdresser now. 
  * 1 p d — p-th hairline grows by d centimeters. 



Note, that in the request 0 Alice is interested in hypothetical scenario of taking a haircut now, so no hairlines change their length.

Input

The first line contains three integers n, m and l (1 ≤ n, m ≤ 100 000, 1 ≤ l ≤ 10^9) — the number of hairlines, the number of requests and the favorite number of Alice.

The second line contains n integers a_i (1 ≤ a_i ≤ 10^9) — the initial lengths of all hairlines of Alice.

Each of the following m lines contains a request in the format described in the statement.

The request description starts with an integer t_i. If t_i = 0, then you need to find the time the haircut would take. Otherwise, t_i = 1 and in this moment one hairline grows. The rest of the line than contains two more integers: p_i and d_i (1 ≤ p_i ≤ n, 1 ≤ d_i ≤ 10^9) — the number of the hairline and the length it grows by.

Output

For each query of type 0 print the time the haircut would take.

Example

Input

4 7 3
1 2 3 4
0
1 2 3
0
1 1 3
0
1 3 1
0


Output

1
2
2
1

Note

Consider the first example:

  * Initially lengths of hairlines are equal to 1, 2, 3, 4 and only 4-th hairline is longer l=3, and hairdresser can cut it in 1 second. 
  * Then Alice's second hairline grows, the lengths of hairlines are now equal to 1, 5, 3, 4 
  * Now haircut takes two seonds: two swings are required: for the 4-th hairline and for the 2-nd. 
  * Then Alice's first hairline grows, the lengths of hairlines are now equal to 4, 5, 3, 4 
  * The haircut still takes two seconds: with one swing hairdresser can cut 4-th hairline and with one more swing cut the segment from 1-st to 2-nd hairline. 
  * Then Alice's third hairline grows, the lengths of hairlines are now equal to 4, 5, 4, 4 
  * Now haircut takes only one second: with one swing it is possible to cut the segment from 1-st hairline to the 4-th. 

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