vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Russian version of the problem can be read here.

There are N boxes where cats can sleep and eat, numbered from the left to the right starting from 1. Each box contains some type of food, which is a positive integer. Initially, the i-th box contains food of type A[i].

A cat will occupy some consecutive subset of boxes, and all the food in the subset must be of the same type.

M events happened. There are events of two types:
Change the food type to type c in all boxes with indices from l to r, inclusve.
Count the number of possible subsets a cat can choose, considering that he is allowed to occupy only boxes with indices from l to r, inclusve.

Your task is to process all the given events.

Input format

The first line of the input contains two integers N and M. The second line contains N space separated integers, which are the array A[i]. The following M lines contain desription of the events, in chronological order. Each line is if format "0 l r c" in case of an event of the first type, and "1 l r" in case of the second one.

Output format

For each event of the second type print the answer to the corresponding event.

Constraints

1 ≤ N, M ≤ 100,000, all types of food are integers between 1 and 1,000,000,000.

SAMPLE INPUT
7 7
1 2 1 1 1 3 3
1 1 7
1 4 7
0 2 6 2
1 1 7
1 2 6
0 2 3 7
1 1 7

SAMPLE OUTPUT
11
6
17
15
11

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Saitama accidentally destroyed a hotel again. To repay the hotel company, Genos has volunteered to operate an elevator in one of its other hotels. The elevator is special — it starts on the top floor, can only move down, and has infinite capacity. Floors are numbered from 0 to s and elevator initially starts on floor s at time 0.

The elevator takes exactly 1 second to move down exactly 1 floor and negligible time to pick up passengers. Genos is given a list detailing when and on which floor passengers arrive. Please determine how long in seconds it will take Genos to bring all passengers to floor 0.


-----Input-----

The first line of input contains two integers n and s (1 ≤ n ≤ 100, 1 ≤ s ≤ 1000) — the number of passengers and the number of the top floor respectively.

The next n lines each contain two space-separated integers f_{i} and t_{i} (1 ≤ f_{i} ≤ s, 1 ≤ t_{i} ≤ 1000) — the floor and the time of arrival in seconds for the passenger number i.


-----Output-----

Print a single integer — the minimum amount of time in seconds needed to bring all the passengers to floor 0.


-----Examples-----
Input
3 7
2 1
3 8
5 2

Output
11

Input
5 10
2 77
3 33
8 21
9 12
10 64

Output
79



-----Note-----

In the first sample, it takes at least 11 seconds to bring all passengers to floor 0. Here is how this could be done:

1. Move to floor 5: takes 2 seconds.

2. Pick up passenger 3.

3. Move to floor 3: takes 2 seconds.

4. Wait for passenger 2 to arrive: takes 4 seconds.

5. Pick up passenger 2.

6. Go to floor 2: takes 1 second.

7. Pick up passenger 1.

8. Go to floor 0: takes 2 seconds.

This gives a total of 2 + 2 + 4 + 1 + 2 = 11 seconds.

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

Time Limit: 1 seconds

Memory Limit: 256 megabytes

Problem Description:
A flea is sitting at one of the *n* hassocks, arranged in a circle, at the moment. After minute number *k* the flea jumps through *k*<=-<=1 hassoсks (clockwise). For example, after the first minute the flea jumps to the neighboring hassock. You should answer: will the flea visit all the hassocks or not. We assume that flea has infinitely much time for this jumping.

Input Specification:
The only line contains single integer: 1<=≤<=*n*<=≤<=1000 — number of hassocks.

Output Specification:
Output "YES" if all the hassocks will be visited and "NO" otherwise.

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

Demo Output:
['YES\n', 'NO\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Boxes And Balls

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Ivan has *n* different boxes. The first of them contains some balls of *n* different colors.

Ivan wants to play a strange game. He wants to distribute the balls into boxes in such a way that for every *i* (1<=≤<=*i*<=≤<=*n*) *i*-th box will contain all balls with color *i*.

In order to do this, Ivan will make some turns. Each turn he does the following:
 1.  Ivan chooses any non-empty box and takes all balls from this box; 1.  Then Ivan chooses any *k* empty boxes (the box from the first step becomes empty, and Ivan is allowed to choose it), separates the balls he took on the previous step into *k* non-empty groups and puts each group into one of the boxes. He should put each group into a separate box. He can choose either *k*<==<=2 or *k*<==<=3. 
The penalty of the turn is the number of balls Ivan takes from the box during the first step of the turn. And penalty of the game is the total penalty of turns made by Ivan until he distributes all balls to corresponding boxes.

Help Ivan to determine the minimum possible penalty of the game!

Input Specification:
The first line contains one integer number *n* (1<=≤<=*n*<=≤<=200000) — the number of boxes and colors.

The second line contains *n* integer numbers *a*1, *a*2, ..., *a**n* (1<=≤<=*a**i*<=≤<=109), where *a**i* is the number of balls with color *i*.

Output Specification:
Print one number — the minimum possible penalty of the game.

Demo Input:
['3\n1 2 3\n', '4\n2 3 4 5\n']

Demo Output:
['6\n', '19\n']

Note:
In the first example you take all the balls from the first box, choose *k* = 3 and sort all colors to corresponding boxes. Penalty is 6.

In the second example you make two turns: 
 1.  Take all the balls from the first box, choose *k* = 3, put balls of color 3 to the third box, of color 4 — to the fourth box and the rest put back into the first box. Penalty is 14; 1.  Take all the balls from the first box, choose *k* = 2, put balls of color 1 to the first box, of color 2 — to the second box. Penalty is 5. 
Total penalty is 19.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
-----Input-----
The first line of input contains a line contains a line with four non-negative integers, $2 \le n \le 250$, $0 \le m \le 5000$, $0 \le s \le n-1$ and $0 \le t \le n-1$, separated by single spaces, where $n$ is the numbers of nodes in the graph, $m$ is the number of edges, $s$ is the source and $t$ is the sink ($s \ne t$). Nodes are numbered from $0$ to $n-1$. Then follow $m$ lines, each line consisting of four (space-separated) integers $u$, $v$, $c$ and $w$ indicating that there is an edge from $u$ to $v$ in the graph with capacity $1 \le c \le 10000$ and cost $1 \le w \le 1000$.

-----Output-----
Output a single line containing two integers; the size $F$ of a maximum flow from node $s$ to node $t$, and the cost of a mimimum cost flow of size $F$. You may assume that $F < 2^{31}$.

-----Examples-----
Sample Input 1:
4 4 0 3
0 1 4 10
1 2 2 10
0 2 4 30
2 3 4 10
Sample Output 1:
4 140

Sample Input 2:
2 1 0 1
0 1 1000 100
Sample Output 2:
1000 100000

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

* **_Given_** *three integers* `a` ,`b` ,`c`, **_return_** *the **_largest number_** obtained after inserting the following operators and brackets*: `+`, `*`, `()`
* In other words , **_try every combination of a,b,c with [*+()] , and return the Maximum Obtained_**
___
# Consider an Example :

**_With the numbers are 1, 2 and 3_** , *here are some ways of placing signs and brackets*:

* `1 * (2 + 3) = 5`
* `1 * 2 * 3 = 6`
* `1 + 2 * 3 = 7`
* `(1 + 2) * 3 = 9`

So **_the maximum value_** that you can obtain is  **_9_**.

___
# Notes 

* **_The numbers_** *are always* **_positive_**. 
* **_The numbers_** *are in the range* **_(1  ≤  a, b, c  ≤  10)_**.
* *You can use the same operation* **_more than once_**.
* **It's not necessary** *to place all the signs and brackets*.
* **_Repetition_** *in numbers may occur* .
* You **_cannot swap the operands_**. For instance, in the given example **_you cannot get expression_** `(1 + 3) * 2 = 8`.

___
# Input >> Output Examples:

```
expressionsMatter(1,2,3)  ==>  return 9
```
## **_Explanation_**:
*After placing signs and brackets, the **_Maximum value_** obtained from the expression* `(1+2) * 3 = 9`.
___

```
expressionsMatter(1,1,1)  ==>  return 3
```
## **_Explanation_**:
*After placing signs, the **_Maximum value_** obtained from the expression is* `1 + 1 + 1 = 3`.
___

```
expressionsMatter(9,1,1)  ==>  return 18
```
## **_Explanation_**:
*After placing signs and brackets, the **_Maximum value_** obtained from the expression is* `9 * (1+1) = 18`.
___
___
___

# [Playing with Numbers Series](https://www.codewars.com/collections/playing-with-numbers)

# [Playing With Lists/Arrays Series](https://www.codewars.com/collections/playing-with-lists-slash-arrays)

# [Bizarre Sorting-katas](https://www.codewars.com/collections/bizarre-sorting-katas)

# [For More Enjoyable Katas](http://www.codewars.com/users/MrZizoScream/authored)
___

## ALL translations are welcomed

## Enjoy Learning !!
# Zizou

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Holiday Of Equality

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
In Berland it is the holiday of equality. In honor of the holiday the king decided to equalize the welfare of all citizens in Berland by the expense of the state treasury. 

Totally in Berland there are *n* citizens, the welfare of each of them is estimated as the integer in *a**i* burles (burle is the currency in Berland).

You are the royal treasurer, which needs to count the minimum charges of the kingdom on the king's present. The king can only give money, he hasn't a power to take away them.

Input Specification:
The first line contains the integer *n* (1<=≤<=*n*<=≤<=100) — the number of citizens in the kingdom.

The second line contains *n* integers *a*1,<=*a*2,<=...,<=*a**n*, where *a**i* (0<=≤<=*a**i*<=≤<=106) — the welfare of the *i*-th citizen.

Output Specification:
In the only line print the integer *S* — the minimum number of burles which are had to spend.

Demo Input:
['5\n0 1 2 3 4\n', '5\n1 1 0 1 1\n', '3\n1 3 1\n', '1\n12\n']

Demo Output:
['10', '1', '4', '0']

Note:
In the first example if we add to the first citizen 4 burles, to the second 3, to the third 2 and to the fourth 1, then the welfare of all citizens will equal 4.

In the second example it is enough to give one burle to the third citizen. 

In the third example it is necessary to give two burles to the first and the third citizens to make the welfare of citizens equal 3.

In the fourth example it is possible to give nothing to everyone because all citizens have 12 burles.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In one well-known algorithm of finding the k-th order statistics we should divide all elements into groups of five consecutive elements and find the median of each five. A median is called the middle element of a sorted array (it's the third largest element for a group of five). To increase the algorithm's performance speed on a modern video card, you should be able to find a sum of medians in each five of the array.

A sum of medians of a sorted k-element set S = {a1, a2, ..., ak}, where a1 < a2 < a3 < ... < ak, will be understood by as 

<image>

The <image> operator stands for taking the remainder, that is <image> stands for the remainder of dividing x by y.

To organize exercise testing quickly calculating the sum of medians for a changing set was needed.

Input

The first line contains number n (1 ≤ n ≤ 105), the number of operations performed.

Then each of n lines contains the description of one of the three operations: 

  * add x — add the element x to the set; 
  * del x — delete the element x from the set; 
  * sum — find the sum of medians of the set. 



For any add x operation it is true that the element x is not included in the set directly before the operation.

For any del x operation it is true that the element x is included in the set directly before the operation.

All the numbers in the input are positive integers, not exceeding 109.

Output

For each operation sum print on the single line the sum of medians of the current set. If the set is empty, print 0.

Please, do not use the %lld specificator to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams (also you may use the %I64d specificator).

Examples

Input

6
add 4
add 5
add 1
add 2
add 3
sum


Output

3


Input

14
add 1
add 7
add 2
add 5
sum
add 6
add 8
add 9
add 3
add 4
add 10
sum
del 1
sum


Output

5
11
13

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Valera is a collector. Once he wanted to expand his collection with exactly one antique item.

Valera knows n sellers of antiques, the i-th of them auctioned k_{i} items. Currently the auction price of the j-th object of the i-th seller is s_{ij}. Valera gets on well with each of the n sellers. He is perfectly sure that if he outbids the current price of one of the items in the auction (in other words, offers the seller the money that is strictly greater than the current price of the item at the auction), the seller of the object will immediately sign a contract with him.

Unfortunately, Valera has only v units of money. Help him to determine which of the n sellers he can make a deal with.


-----Input-----

The first line contains two space-separated integers n, v (1 ≤ n ≤ 50; 10^4 ≤ v ≤ 10^6) — the number of sellers and the units of money the Valera has.

Then n lines follow. The i-th line first contains integer k_{i} (1 ≤ k_{i} ≤ 50) the number of items of the i-th seller. Then go k_{i} space-separated integers s_{i}1, s_{i}2, ..., s_{ik}_{i} (10^4 ≤ s_{ij} ≤ 10^6) — the current prices of the items of the i-th seller. 


-----Output-----

In the first line, print integer p — the number of sellers with who Valera can make a deal.

In the second line print p space-separated integers q_1, q_2, ..., q_{p} (1 ≤ q_{i} ≤ n) — the numbers of the sellers with who Valera can make a deal. Print the numbers of the sellers in the increasing order. 


-----Examples-----
Input
3 50000
1 40000
2 20000 60000
3 10000 70000 190000

Output
3
1 2 3

Input
3 50000
1 50000
3 100000 120000 110000
3 120000 110000 120000

Output
0




-----Note-----

In the first sample Valera can bargain with each of the sellers. He can outbid the following items: a 40000 item from the first seller, a 20000 item from the second seller, and a 10000 item from the third seller.

In the second sample Valera can not make a deal with any of the sellers, as the prices of all items in the auction too big for him.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
zscoder wants to generate an input file for some programming competition problem.

His input is a string consisting of n letters 'a'. He is too lazy to write a generator so he will manually generate the input in a text editor.

Initially, the text editor is empty. It takes him x seconds to insert or delete a letter 'a' from the text file and y seconds to copy the contents of the entire text file, and duplicate it.

zscoder wants to find the minimum amount of time needed for him to create the input file of exactly n letters 'a'. Help him to determine the amount of time needed to generate the input.


-----Input-----

The only line contains three integers n, x and y (1 ≤ n ≤ 10^7, 1 ≤ x, y ≤ 10^9) — the number of letters 'a' in the input file and the parameters from the problem statement.


-----Output-----

Print the only integer t — the minimum amount of time needed to generate the input file.


-----Examples-----
Input
8 1 1

Output
4

Input
8 1 10

Output
8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Heidi is a statistician to the core, and she likes to study the evolution of marmot populations in each of V (1 ≤ V ≤ 100) villages! So it comes that every spring, when Heidi sees the first snowdrops sprout in the meadows around her barn, she impatiently dons her snowshoes and sets out to the Alps, to welcome her friends the marmots to a new season of thrilling adventures.

Arriving in a village, Heidi asks each and every marmot she comes across for the number of inhabitants of that village. This year, the marmots decide to play an April Fools' joke on Heidi. Instead of consistently providing the exact number of inhabitants P (10 ≤ P ≤ 1000) of the village, they respond with a random non-negative integer k, drawn from one of two types of probability distributions:

  * Poisson (d'avril) distribution: the probability of getting an answer k is <image> for k = 0, 1, 2, 3, ..., 
  * Uniform distribution: the probability of getting an answer k is <image> for k = 0, 1, 2, ..., 2P. 



Heidi collects exactly 250 answers per village. Every village follows either the Poisson or the uniform distribution. Heidi cannot tell marmots apart, so she may query some marmots several times, and each time the marmot will answer with a new number drawn from the village's distribution.

Can you help Heidi to find out whether a village follows a Poisson or a uniform distribution?

Input

The first line of input will contain the number of villages V (1 ≤ V ≤ 100). The following V lines each describe one village. The description of each village consists of 250 space-separated integers k, drawn from one of the above distributions.

Output

Output one line per village, in the same order as provided in the input. The village's line shall state poisson if the village's distribution is of the Poisson type, and uniform if the answer came from a uniform distribution.

Example

Input

2
92 100 99 109 93 105 103 106 101 99 ... (input is truncated)
28 180 147 53 84 80 180 85 8 16 ... (input is truncated)

Output

poisson
uniform

Note

The full example input is visually represented below, along with the probability distribution function it was drawn from (the y-axis is labeled by its values multiplied by 250).

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Daddy of Tim and Bob may be a normal businessman in the eyes of the world, but secretly he owns the world’s longest garden (don't ask where, its highly confidential). But as he was very busy in his work, so he was not able to take care of his garden. So this Sunday he decided to spent his time in doing garden’s work.  Over the years Daddy has planted n plants in his garden, of m different plant species numbered from 1 to m. His garden is very narrow and can be viewed as an infinite line, with each plant occupying a single point on that line.

Once he read in a magazine  that each species of plant thrives at a different temperature, so he wants to arrange m - 1 borders that would divide the garden into m sections numbered from 1 to m from left to right with each section housing a single species. He is free to place the borders, but in the end all of the i-th species plants must reside in i-th section from the left.

Of course, it is not always possible to place the borders in such way, so Daddy needs to replant some of his plants. He can remove each plant from its position and place it anywhere in the garden (at any real coordinate) with no plant already in it. Since replanting is a lot of stress for the plants,  as now you too know Daddy’s secret help him to find the minimum number of plants he has to replant to be able to place the borders.

Input

The first line of input contains number of test cases.
Each test case contains two space-separated integers n and m(1 ≤ n, m ≤ 5000, n ≥ m), the number of plants and the number of different species respectively.  Each of the following n lines contain two space-separated numbers: one integer number s[i] (1 ≤ si ≤ m), and one real number x[i] (0 ≤ x[i] ≤ 6000), the species and position of the i-th plant. Each x[i] will contain no more than 6 digits after the decimal point. It is guaranteed that all x[i] are different; there is at least one plant of each species; the plants are given in order "from left to the right", that is in the ascending order of their xi coordinates (x[i] < x[i] + 1, 1 ≤ i < n).

Output

For each test case output the minimum number of plants to be replanted.

Constraints

As mentioned input part.

SAMPLE INPUT
2
5 5
5 0
4 1
3 2
2 3
1 4
3 3
2 0
1 1
3 2

SAMPLE OUTPUT
4
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A permutation is a sequence of n integers from 1 to n, in which all the numbers occur exactly once. For example, [1], [3, 5, 2, 1, 4], [1, 3, 2] are permutations, and [2, 3, 2], [4, 3, 1], [0] are not.

Polycarp was given four integers n, l, r (1 ≤ l ≤ r ≤ n) and s (1 ≤ s ≤ (n (n+1))/(2)) and asked to find a permutation p of numbers from 1 to n that satisfies the following condition: 

  * s = p_l + p_{l+1} + … + p_r. 



For example, for n=5, l=3, r=5, and s=8, the following permutations are suitable (not all options are listed): 

  * p = [3, 4, 5, 2, 1]; 
  * p = [5, 2, 4, 3, 1]; 
  * p = [5, 2, 1, 3, 4]. 

But, for example, there is no permutation suitable for the condition above for n=4, l=1, r=1, and s=5.

Help Polycarp, for the given n, l, r, and s, find a permutation of numbers from 1 to n that fits the condition above. If there are several suitable permutations, print any of them.

Input

The first line contains a single integer t (1 ≤ t ≤ 500). Then t test cases follow.

Each test case consist of one line with four integers n (1 ≤ n ≤ 500), l (1 ≤ l ≤ n), r (l ≤ r ≤ n), s (1 ≤ s ≤ (n (n+1))/(2)).

It is guaranteed that the sum of n for all input data sets does not exceed 500.

Output

For each test case, output on a separate line: 

  * n integers — a permutation of length n that fits the condition above if such a permutation exists; 
  * -1, otherwise. 



If there are several suitable permutations, print any of them.

Example

Input


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


Output


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

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

Write a function, `nicknameGenerator` that takes a string name as an argument and returns the first 3 or 4 letters as a nickname.

If the 3rd letter is a consonant, return the first 3 letters.

If the 3rd letter is a vowel, return the first 4 letters. 

If the string is less than 4 characters, return "Error: Name too short".

**Notes:**

- Vowels are "aeiou", so discount the letter "y".
- Input will always be a string.
- Input will always have the first letter capitalised and the rest lowercase (e.g. Sam).
- The input can be modified

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