vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You have a string $s$ — a sequence of commands for your toy robot. The robot is placed in some cell of a rectangular grid. He can perform four commands:  'W' — move one cell up;  'S' — move one cell down;  'A' — move one cell left;  'D' — move one cell right. 

Let $Grid(s)$ be the grid of minimum possible area such that there is a position in the grid where you can place the robot in such a way that it will not fall from the grid while running the sequence of commands $s$. For example, if $s = \text{DSAWWAW}$ then $Grid(s)$ is the $4 \times 3$ grid:  you can place the robot in the cell $(3, 2)$;  the robot performs the command 'D' and moves to $(3, 3)$;  the robot performs the command 'S' and moves to $(4, 3)$;  the robot performs the command 'A' and moves to $(4, 2)$;  the robot performs the command 'W' and moves to $(3, 2)$;  the robot performs the command 'W' and moves to $(2, 2)$;  the robot performs the command 'A' and moves to $(2, 1)$;  the robot performs the command 'W' and moves to $(1, 1)$.  [Image] 

You have $4$ extra letters: one 'W', one 'A', one 'S', one 'D'. You'd like to insert at most one of these letters in any position of sequence $s$ to minimize the area of $Grid(s)$.

What is the minimum area of $Grid(s)$ you can achieve?


-----Input-----

The first line contains one integer $T$ ($1 \le T \le 1000$) — the number of queries.

Next $T$ lines contain queries: one per line. This line contains single string $s$ ($1 \le |s| \le 2 \cdot 10^5$, $s_i \in \{\text{W}, \text{A}, \text{S}, \text{D}\}$) — the sequence of commands.

It's guaranteed that the total length of $s$ over all queries doesn't exceed $2 \cdot 10^5$.


-----Output-----

Print $T$ integers: one per query. For each query print the minimum area of $Grid(s)$ you can achieve.


-----Example-----
Input
3
DSAWWAW
D
WA

Output
8
2
4



-----Note-----

In the first query you have to get string $\text{DSAWW}\underline{D}\text{AW}$.

In second and third queries you can not decrease the area of $Grid(s)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mirko and Slavko are playing a new game, “Trojke” (Triplets, in English). First they use a chalk to draw an $N \times N$ square grid on the road. Then they write letters into some of the squares. No letter is written more than once in the grid.

The game consists of trying to find three letters on a line as fast as possible. Three letters are considered to be on the same line if there is a line going through the centre of each of the three squares.

After a while it gets harder to find new triplets. Mirko and Slavko need a program that counts all the triplets, so that they know if the game is over or they need to search further.

-----Input-----
The first line contains an integer $N$ ($3 \le N \le 100$), the dimension of the grid.

Each of the $N$ following lines contains $N$ characters describing the grid – uppercase letters and the character ’.’ which marks an empty square.

-----Output-----
Output the number of triples on a single line.

-----Examples-----
Sample Input 1:
4
...D
..C.
.B..
A...
Sample Output 1:
4

Sample Input 2:
5
..T..
A....
.FE.R
....X
S....
Sample Output 2:
3

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Arkady decides to observe a river for *n* consecutive days. The river's water level on each day is equal to some real value.

Arkady goes to the riverside each day and makes a mark on the side of the channel at the height of the water level, but if it coincides with a mark made before, no new mark is created. The water does not wash the marks away. Arkady writes down the number of marks strictly above the water level each day, on the *i*-th day this value is equal to *m**i*.

Define *d**i* as the number of marks strictly under the water level on the *i*-th day. You are to find out the minimum possible sum of *d**i* over all days. There are no marks on the channel before the first day.

Input Specification:
The first line contains a single positive integer *n* (1<=≤<=*n*<=≤<=105) — the number of days.

The second line contains *n* space-separated integers *m*1,<=*m*2,<=...,<=*m**n* (0<=≤<=*m**i*<=&lt;<=*i*) — the number of marks strictly above the water on each day.

Output Specification:
Output one single integer — the minimum possible sum of the number of marks strictly below the water level among all days.

Demo Input:
['6\n0 1 0 3 0 2\n', '5\n0 1 2 1 2\n', '5\n0 1 1 2 2\n']

Demo Output:
['6\n', '1\n', '0\n']

Note:
In the first example, the following figure shows an optimal case.

Note that on day 3, a new mark should be created because if not, there cannot be 3 marks above water on day 4. The total number of marks underwater is 0 + 0 + 2 + 0 + 3 + 1 = 6.

In the second example, the following figure shows an optimal case.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
At the children's day, the child came to Picks's house, and messed his house up. Picks was angry at him. A lot of important things were lost, in particular the favorite sequence of Picks.

Fortunately, Picks remembers how to repair the sequence. Initially he should create an integer array a[1], a[2], ..., a[n]. Then he should perform a sequence of m operations. An operation can be one of the following:

  1. Print operation l, r. Picks should write down the value of <image>. 
  2. Modulo operation l, r, x. Picks should perform assignment a[i] = a[i] mod x for each i (l ≤ i ≤ r). 
  3. Set operation k, x. Picks should set the value of a[k] to x (in other words perform an assignment a[k] = x). 



Can you help Picks to perform the whole sequence of operations?

Input

The first line of input contains two integer: n, m (1 ≤ n, m ≤ 105). The second line contains n integers, separated by space: a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 109) — initial value of array elements.

Each of the next m lines begins with a number type <image>. 

  * If type = 1, there will be two integers more in the line: l, r (1 ≤ l ≤ r ≤ n), which correspond the operation 1. 
  * If type = 2, there will be three integers more in the line: l, r, x (1 ≤ l ≤ r ≤ n; 1 ≤ x ≤ 109), which correspond the operation 2. 
  * If type = 3, there will be two integers more in the line: k, x (1 ≤ k ≤ n; 1 ≤ x ≤ 109), which correspond the operation 3. 

Output

For each operation 1, please print a line containing the answer. Notice that the answer may exceed the 32-bit integer.

Examples

Input

5 5
1 2 3 4 5
2 3 5 4
3 3 5
1 2 5
2 1 3 3
1 1 3


Output

8
5


Input

10 10
6 9 6 7 6 1 10 10 9 5
1 3 9
2 7 10 9
2 5 10 8
1 4 7
3 3 7
2 7 9 9
1 2 4
1 6 6
1 5 9
3 1 10


Output

49
15
23
1
9

Note

Consider the first testcase:

  * At first, a = {1, 2, 3, 4, 5}. 
  * After operation 1, a = {1, 2, 3, 0, 1}. 
  * After operation 2, a = {1, 2, 5, 0, 1}. 
  * At operation 3, 2 + 5 + 0 + 1 = 8. 
  * After operation 4, a = {1, 2, 2, 0, 1}. 
  * At operation 5, 1 + 2 + 2 = 5. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An electronics shop sells red and blue lamps. A red lamp costs X rupees and a blue lamp costs Y rupees.

Chef is going to buy exactly N lamps from this shop. Find the minimum amount of money Chef needs to pay such that at least K of the lamps bought are red.

------ 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 containing four space-separated integers N, K, X, Y.

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

For each test case, output on a new line the minimum amount of money Chef needs to pay in order to buy N lamps such that at least K of the lamps bought are red.

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

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤10^{8}$
$0 ≤ K ≤ N$
$1 ≤ X, Y ≤10$

----- Sample Input 1 ------ 
4
2 2 5 1
4 1 3 1
3 0 4 7
5 2 3 4

----- Sample Output 1 ------ 
10
6
12
15

----- explanation 1 ------ 
Test case $1$: Chef buys $2$ red lamps with $2 \cdot 5 = 10$ rupees.

Test case $2$: Chef buys $1$ red lamp and $3$ blue lamps with $1 \cdot 3 + 3\cdot 1 = 6$ rupees.

Test case $3$: Chef buys $3$ red lamps with $3 \cdot 4 = 12$ rupees.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array of positive integers a_1, a_2, ..., a_{n} × T of length n × T. We know that for any i > n it is true that a_{i} = a_{i} - n. Find the length of the longest non-decreasing sequence of the given array.


-----Input-----

The first line contains two space-separated integers: n, T (1 ≤ n ≤ 100, 1 ≤ T ≤ 10^7). The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 300).


-----Output-----

Print a single number — the length of a sought sequence.


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

Output
5



-----Note-----

The array given in the sample looks like that: 3, 1, 4, 2, 3, 1, 4, 2, 3, 1, 4, 2. The elements in bold form the largest non-decreasing subsequence.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N squares in a row, numbered 1 through N from left to right. Snuke and Rng are playing a board game using these squares, described below:

1. First, Snuke writes an integer into each square.
2. Each of the two players possesses one piece. Snuke places his piece onto square 1, and Rng places his onto square 2.
3. The player whose piece is to the left of the opponent's, moves his piece. The destination must be a square to the right of the square where the piece is currently placed, and must not be a square where the opponent's piece is placed.
4. Repeat step 3. When the pieces cannot be moved any more, the game ends.
5. The score of each player is calculated as the sum of the integers written in the squares where the player has placed his piece before the end of the game.



Snuke has already written an integer A_i into square i (1≦i≦N-1), but not into square N yet. He has decided to calculate for each of M integers X_1,X_2,...,X_M, if he writes it into square N and the game is played, what the value "(Snuke's score) - (Rng's score)" will be. Here, it is assumed that each player moves his piece to maximize the value "(the player's score) - (the opponent's score)".

Constraints

* 3≦N≦200,000
* 0≦A_i≦10^6
* The sum of all A_i is at most 10^6.
* 1≦M≦200,000
* 0≦X_i≦10^9

Input

The input is given from Standard Input in the following format:


N
A_1 A_2 ... A_{N-1}
M
X_1
X_2
:
X_M


Output

For each of the M integers X_1, ..., X_M, print the value "(Snuke's score) - (Rng's score)" if it is written into square N, one per line.

Examples

Input

5
2 7 1 8
1
2


Output

0


Input

9
2 0 1 6 1 1 2 6
5
2016
1
1
2
6


Output

2001
6
6
7
7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chefina  is  always interested to play with string. But due to exam pressure she has no time to solve a string problem. She wants your help. Can you help her to solve that problem?
You are given a string. You have to find out the $Wonder$ $Sum$ of the string. $Wonder$ $Sum$ of a string is defined as the sum of the value of each character of the string. 
The value of each character means:
- If the string is started with "a" , then the value of each character of the string is like "a"=100, "b"=101, "c"="102" ………"z"=125.
- If the string is started with "z" , then the value of each character of the string is like "a"=2600, "b"=2601, "c"="2602" ………"z"=2625.
Since even the $Wonder$ $Sum$ can be large, output $Wonder$ $Sum$ modulo  ($10^9 + 7$).

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, a string $S$ with lower case alphabet 
only.

-----Output:-----
For each testcase, output in a single line integer i.e.  $Wonder$ $Sum$ modulo  ($10^9 + 7$).

-----Constraints-----
- $1 \leq T \leq 1000$
- $1 \leq |S| \leq 10^5$

-----Sample Input:-----
$2$$cab$
$sdef$

-----Sample Output:-----
$903$
$7630$

-----EXPLANATION:-----
i) For the first test case, since the string is started with "$c$", so output is ($302$+$300$+$301$)=$903$
ii)For the second test case, since the string is started with "$s$", so output is ($1918$+$1903$+$1904$+$1905$)=$7630$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Warning: This problem has an unusual memory limit!

Bob decided that he will not waste his prime years implementing GUI forms for a large corporation and instead will earn his supper on the Stock Exchange Reykjavik. The Stock Exchange Reykjavik is the only actual stock exchange in the world. The only type of transaction is to take a single share of stock x and exchange it for a single share of stock y, provided that the current price of share x is at least the current price of share y. 

There are 2n stocks listed on the SER that are of interest to Bob, numbered from 1 to 2n. Bob owns a single share of stocks 1 through n and would like to own a single share of each of n+1 through 2n some time in the future.

Bob managed to forecast the price of each stock — in time t ≥ 0, the stock i will cost a_i ⋅ ⌊ t ⌋ + b_i. The time is currently t = 0. Help Bob find the earliest moment in time in which he can own a single share of each of n+1 through 2n, and the minimum number of stock exchanges he has to perform in order to do that.

You may assume that the Stock Exchange has an unlimited amount of each stock at any point in time. 

Input

The first line contains a single integer n (1 ≤ n ≤ 2200) — the number stocks currently owned by Bob.

Each of the next 2n lines contains integers a_i and b_i (0 ≤ a_i, b_i ≤ 10^9), representing the stock price of stock i. 

Output

If it is impossible for Bob to achieve his goal, output a single integer -1.

Otherwise, output two integers T and E, where T is the minimum time in which he can achieve his goal, and E is the minimum number of exchanges in which he can achieve his goal at time T.

Examples

Input


1
3 10
1 16


Output


3 1


Input


2
3 0
2 1
1 10
1 11


Output


6 3


Input


1
42 42
47 47


Output


-1


Input


8
145 1729363
891 4194243
424 853731
869 1883440
843 556108
760 1538373
270 762781
986 2589382
610 99315884
591 95147193
687 99248788
65 95114537
481 99071279
293 98888998
83 99764577
769 96951171


Output


434847 11


Input


8
261 261639
92 123277
271 131614
320 154417
97 258799
246 17926
117 222490
110 39356
85 62864876
86 62781907
165 62761166
252 62828168
258 62794649
125 62817698
182 62651225
16 62856001


Output


1010327 11

Note

In the first example, Bob simply waits until time t = 3, when both stocks cost exactly the same amount.

In the second example, the optimum strategy is to exchange stock 2 for stock 1 at time t = 1, then exchange one share of stock 1 for stock 3 at time t = 5 (where both cost 15) and then at time t = 6 exchange the second on for the stock number 4 (when they cost 18 and 17, respectively). Note that he can achieve his goal also with only two exchanges, but this would take total time of t = 9, when he would finally be able to exchange the share number 2 for the share number 3. 

In the third example, Bob can never achieve his goal, as the second stock is always strictly more expensive than the first one.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After Curiosity discovered not just water on Mars, but also an aggressive, bloodthirsty bunch of aliens, the Louvain-la-Neuve municipal government decided to take precautionary measures; they built shelters in order to shelter everyone in the city in the event of an extraterrestial attack.

Several alien-proof shelters have been erected throughout the city, where citizens can weather an alien invasion. However, due to municipal regulations and local building codes the shelters are limited in size. This makes it necessary for the government to assign every citizen a shelter to calmly direct themselves towards in the rare event of a fleet of UFOs blotting out the sun. Conditional on no shelter being assigned more people than it can fit, it is of the utmost importance that the time it takes until everyone has arrived at a shelter is minimized.

We model Louvain-la-Neuve as a network of $n$ locations at which people live, connected by $m$ bidirectional roads. Located at $s$ points throughout the city are the shelters, each with a given maximum capacity. What is the minimum amount of time it takes for everyone to arrive at a shelter, when we assign people to shelters optimally?

The Louvain-la-Neuve municipal government has made sure that there is enough shelter capacity for its citizens and all shelters can be reached from any location, i.e. it is always possible to shelter everyone in some way.

-----Input-----
 - On the first line are three integers, the number of locations $1 \leq n \leq 10^5$, roads $0 \leq m \leq 2\cdot 10^5$, and shelters $1 \leq s \leq 10$.
 - Then follows a line with $n$ integers $0 \leq p_ i \leq 10^9$, indicating the the number of people living at location $1 \leq i \leq n$.
 - Then follow $m$ lines containing three integers $1 \leq u, v \leq n$ and $1 \leq w \leq 10^9$ indicating that there is a bidirectional road connecting $u$ and $v$ that takes $w$ time to traverse. For any two locations there is at most one road connecting them directly, and no road connects a location to itself.
 - Finally follow $s$ lines with two integers $1 \leq s_ i \leq n$ and $1 \leq c_ i \leq 10^9$, indicating that there is a shelter with capacity $c_ i$ at location $s_ i$.

-----Output-----
Print the minimum amount of time it takes to shelter everyone.

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

Sample Input 2:
4 5 2
2 0 0 2
1 2 6
1 3 2
2 3 3
3 4 4
4 2 6
3 2
2 2
Sample Output 2:
5

Sample Input 3:
7 8 3
0 1 1 1 1 0 2
1 2 1
2 3 1
3 1 1
4 6 5
4 3 1
6 7 10
7 5 3
5 6 3
6 5
1 1
2 1
Sample Output 3:
6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp plays a computer game. In this game, the players summon armies of magical minions, which then fight each other.

Polycarp can summon $n$ different minions. The initial power level of the $i$-th minion is $a_i$, and when it is summoned, all previously summoned minions' power levels are increased by $b_i$. The minions can be summoned in any order.

Unfortunately, Polycarp cannot have more than $k$ minions under his control. To get rid of unwanted minions after summoning them, he may destroy them. Each minion can be summoned (and destroyed) only once.

Polycarp's goal is to summon the strongest possible army. Formally, he wants to maximize the sum of power levels of all minions under his control (those which are summoned and not destroyed).

Help Polycarp to make up a plan of actions to summon the strongest possible army!


-----Input-----

The first line contains one integer $T$ ($1 \le T \le 75$) — the number of test cases.

Each test case begins with a line containing two integers $n$ and $k$ ($1 \le k \le n \le 75$) — the number of minions availible for summoning, and the maximum number of minions that can be controlled by Polycarp, respectively.

Then $n$ lines follow, the $i$-th line contains $2$ integers $a_i$ and $b_i$ ($1 \le a_i \le 10^5$, $0 \le b_i \le 10^5$) — the parameters of the $i$-th minion.


-----Output-----

For each test case print the optimal sequence of actions as follows:

Firstly, print $m$ — the number of actions which Polycarp has to perform ($0 \le m \le 2n$). Then print $m$ integers $o_1$, $o_2$, ..., $o_m$, where $o_i$ denotes the $i$-th action as follows: if the $i$-th action is to summon the minion $x$, then $o_i = x$, and if the $i$-th action is to destroy the minion $x$, then $o_i = -x$. Each minion can be summoned at most once and cannot be destroyed before being summoned (and, obviously, cannot be destroyed more than once). The number of minions in Polycarp's army should be not greater than $k$ after every action.

If there are multiple optimal sequences, print any of them.


-----Example-----
Input
3
5 2
5 3
7 0
5 0
4 0
10 0
2 1
10 100
50 10
5 5
1 5
2 4
3 3
4 2
5 1

Output
4
2 1 -1 5
1
2
5
5 4 3 2 1



-----Note-----

Consider the example test.

In the first test case, Polycarp can summon the minion $2$ with power level $7$, then summon the minion $1$, which will increase the power level of the previous minion by $3$, then destroy the minion $1$, and finally, summon the minion $5$. After this, Polycarp will have two minions with power levels of $10$.

In the second test case, Polycarp can control only one minion, so he should choose the strongest of them and summon it.

In the third test case, Polycarp is able to summon and control all five minions.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N boxes arranged in a row.
Initially, the i-th box from the left contains a_i candies.
Snuke can perform the following operation any number of times:
 - Choose a box containing at least one candy, and eat one of the candies in the chosen box.
His objective is as follows:
 - Any two neighboring boxes contain at most x candies in total.
Find the minimum number of operations required to achieve the objective.

-----Constraints-----
 - 2 ≤ N ≤ 10^5
 - 0 ≤ a_i ≤ 10^9
 - 0 ≤ x ≤ 10^9

-----Input-----
The input is given from Standard Input in the following format:
N x
a_1 a_2 ... a_N

-----Output-----
Print the minimum number of operations required to achieve the objective.

-----Sample Input-----
3 3
2 2 2

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

Eat one candy in the second box.
Then, the number of candies in each box becomes (2, 1, 2).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are two (6-sided) dice: a red die and a blue die. When a red die is rolled, it shows i with probability p_i percents, and when a blue die is rolled, it shows j with probability q_j percents.

Petr and tourist are playing the following game. Both players know the probabilistic distributions of the two dice. First, Petr chooses a die in his will (without showing it to tourist), rolls it, and tells tourist the number it shows. Then, tourist guesses the color of the chosen die. If he guesses the color correctly, tourist wins. Otherwise Petr wins.

If both players play optimally, what is the probability that tourist wins the game?

Constraints

* 0 ≤ p_i, q_i ≤ 100
* p_1 + ... + p_6 = q_1 + ... + q_6 = 100
* All values in the input are integers.

Input

The input is given from Standard Input in the following format:


p_1 p_2 p_3 p_4 p_5 p_6
q_1 q_2 q_3 q_4 q_5 q_6


Output

Print the probability that tourist wins. The absolute error or the relative error must be at most 10^{-9}.

Examples

Input

25 25 25 25 0 0
0 0 0 0 50 50


Output

1.000000000000


Input

10 20 20 10 20 20
20 20 20 10 10 20


Output

0.550000000000

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