vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Greg is a beginner bodybuilder. Today the gym coach gave him the training plan. All it had was n integers a_1, a_2, ..., a_{n}. These numbers mean that Greg needs to do exactly n exercises today. Besides, Greg should repeat the i-th in order exercise a_{i} times.

Greg now only does three types of exercises: "chest" exercises, "biceps" exercises and "back" exercises. Besides, his training is cyclic, that is, the first exercise he does is a "chest" one, the second one is "biceps", the third one is "back", the fourth one is "chest", the fifth one is "biceps", and so on to the n-th exercise.

Now Greg wonders, which muscle will get the most exercise during his training. We know that the exercise Greg repeats the maximum number of times, trains the corresponding muscle the most. Help Greg, determine which muscle will get the most training.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 20). The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 25) — the number of times Greg repeats the exercises.


-----Output-----

Print word "chest" (without the quotes), if the chest gets the most exercise, "biceps" (without the quotes), if the biceps gets the most exercise and print "back" (without the quotes) if the back gets the most exercise.

It is guaranteed that the input is such that the answer to the problem is unambiguous.


-----Examples-----
Input
2
2 8

Output
biceps

Input
3
5 1 10

Output
back

Input
7
3 3 2 7 9 6 8

Output
chest



-----Note-----

In the first sample Greg does 2 chest, 8 biceps and zero back exercises, so the biceps gets the most exercises.

In the second sample Greg does 5 chest, 1 biceps and 10 back exercises, so the back gets the most exercises.

In the third sample Greg does 18 chest, 12 biceps and 8 back exercises, so the chest gets the most exercise.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ashish runs a small business but he is weak at managing his accounts, though he has managed to calculate his daily expenses. He wishes to find the days between which he had the maximum profit. So, he hires you to make his job simpler for future.
(Profits are positive & Losses are negative numbers)

He gives you the expenses on each day in the form of an array. He requests you to give him the first and the last day of the days he made the maximum profit.

Input Format
First line contains N, the total number of days given.
Second line contains N integers separated by space representing expense on each day.

Output Format
Output contains a single line containing two integers separated by space representing the first and the last day resp.

Example
Input :

5

5  -8   2   6   -1

Output :

3   4

SAMPLE INPUT
5
5 -8 2 6 -1

SAMPLE OUTPUT
3 4

Explanation

First day profit was 5 but on second day he had a loss of 8. And on 3rd and 4th day he manages to earn 8 which is even higher than the first day. So, answer is 3 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Awruk is taking part in elections in his school. It is the final round. He has only one opponent — Elodreip. The are $n$ students in the school. Each student has exactly $k$ votes and is obligated to use all of them. So Awruk knows that if a person gives $a_i$ votes for Elodreip, than he will get exactly $k - a_i$ votes from this person. Of course $0 \le k - a_i$ holds.

Awruk knows that if he loses his life is over. He has been speaking a lot with his friends and now he knows $a_1, a_2, \dots, a_n$ — how many votes for Elodreip each student wants to give. Now he wants to change the number $k$ to win the elections. Of course he knows that bigger $k$ means bigger chance that somebody may notice that he has changed something and then he will be disqualified.

So, Awruk knows $a_1, a_2, \dots, a_n$ — how many votes each student will give to his opponent. Help him select the smallest winning number $k$. In order to win, Awruk needs to get strictly more votes than Elodreip.


-----Input-----

The first line contains integer $n$ ($1 \le n \le 100$) — the number of students in the school.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 100$) — the number of votes each student gives to Elodreip.


-----Output-----

Output the smallest integer $k$ ($k \ge \max a_i$) which gives Awruk the victory. In order to win, Awruk needs to get strictly more votes than Elodreip.


-----Examples-----
Input
5
1 1 1 5 1

Output
5
Input
5
2 2 3 2 2

Output
5


-----Note-----

In the first example, Elodreip gets $1 + 1 + 1 + 5 + 1 = 9$ votes. The smallest possible $k$ is $5$ (it surely can't be less due to the fourth person), and it leads to $4 + 4 + 4 + 0 + 4 = 16$ votes for Awruk, which is enough to win.

In the second example, Elodreip gets $11$ votes. If $k = 4$, Awruk gets $9$ votes and loses to Elodreip.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# The museum of incredible dull things

The museum of incredible dull things wants to get rid of some exhibitions. Miriam, the interior architect, comes up with a plan to remove the most boring exhibitions. She gives them a rating, and then removes the one with the lowest rating.

However, just as she finished rating all exhibitions, she's off to an important fair, so she asks you to write a program that tells her the ratings of the items after one removed the lowest one. Fair enough.

# Task

Given an array of integers, remove the smallest value. **Do not mutate the original array/list**. If there are multiple elements with the same value, remove the one with a lower index. If you get an empty array/list, return an empty array/list.

Don't change the order of the elements that are left.

### Examples

```python
remove_smallest([1,2,3,4,5]) = [2,3,4,5]
remove_smallest([5,3,2,1,4]) = [5,3,2,4]
remove_smallest([2,2,1,2,1]) = [2,2,2,1]
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Valera loves segments. He has recently come up with one interesting problem.

The Ox axis of coordinates has n segments, the i-th segment starts in position li and ends in position ri (we will mark it as [li, ri]). Your task is to process m queries, each consists of number cnti and a set of cnti coordinates of points located on the Ox axis. The answer to the query is the number of segments, such that each of them contains at least one point from the query. Segment [l, r] contains point q, if l ≤ q ≤ r.

Valera found the solution of this problem too difficult. So he asked you to help him. Help Valera. 

Input

The first line contains two integers n, m (1 ≤ n, m ≤ 3·105) — the number of segments on the axis of coordinates and the number of queries. 

Next n lines contain the descriptions of the segments. The i-th line contains two positive integers li, ri (1 ≤ li ≤ ri ≤ 106) — the borders of the i-th segment.

Next m lines contain the description of the queries, one per line. Each line starts from integer cnti (1 ≤ cnti ≤ 3·105) — the number of points in the i-th query. Then the line contains cnti distinct positive integers p1, p2, ..., pcnti (1 ≤ p1 < p2 < ... < pcnti ≤ 106) — the coordinates of points in the i-th query.

It is guaranteed that the total number of points in all queries doesn't exceed 3·105. 

Output

Print m non-negative integers, where the i-th number is the response to the i-th query.

Examples

Input

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


Output

3
1
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N panels arranged in a row in Takahashi's house, numbered 1 through N. The i-th panel has a number A_i written on it. Takahashi is playing by throwing balls at these panels.

Takahashi threw a ball K times. Let the panel hit by a boll in the i-th throw be panel p_i. He set the score for the i-th throw as i \times A_{p_i}.

He was about to calculate the total score for his throws, when he realized that he forgot the panels hit by balls, p_1,p_2,...,p_K. The only fact he remembers is that for every i (1 ≦ i ≦ K-1), 1 ≦ p_{i+1}-p_i ≦ M holds. Based on this fact, find the maximum possible total score for his throws.

Constraints

* 1 ≦ M ≦ N ≦ 100,000
* 1 ≦ K ≦ min(300,N)
* 1 ≦ A_i ≦ 10^{9}

Input

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


N M K
A_1 A_2 … A_N


Output

Print the maximum possible total score for Takahashi's throws.

Examples

Input

5 2 3
10 2 8 10 2


Output

56


Input

5 5 2
5 2 10 5 9


Output

28


Input

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


Output

5000000078

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Linear Kingdom has exactly one tram line. It has `n` stops, numbered from 1 to n in the order of tram's movement. At the i-th stop ai passengers exit the tram, while bi passengers enter it. The tram is empty before it arrives at the first stop.

## Your task

Calculate the tram's minimum capacity such that the number of people inside the tram never exceeds this capacity at any time. Note that at each stop all exiting passengers exit before any entering passenger enters the tram.

## Example

```c++
tram(4, {0, 2, 4, 4}, {3, 5, 2, 0}) ==> 6
```
  
Explaination:
* The number of passengers inside the tram before arriving is 0.
* At the first stop 3 passengers enter the tram, and the number of passengers inside the tram becomes 3.
* At the second stop 2 passengers exit the tram (1 passenger remains inside). Then 5 passengers enter the tram. There are 6 passengers inside the tram now.
* At the third stop 4 passengers exit the tram (2 passengers remain inside). Then 2 passengers enter the tram. There are 4 passengers inside the tram now.
* Finally, all the remaining passengers inside the tram exit the tram at the last stop. There are no passenger inside the tram now, which is in line with the constraints.

Since the number of passengers inside the tram never exceeds 6, a capacity of 6 is sufficient. Furthermore it is not possible for the tram to have a capacity less than 6. Hence, 6 is the correct answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this problem at each moment you have a set of intervals. You can move from interval (a, b) from our set to interval (c, d) from our set if and only if c < a < d or c < b < d. Also there is a path from interval I_1 from our set to interval I_2 from our set if there is a sequence of successive moves starting from I_1 so that we can reach I_2.

Your program should handle the queries of the following two types:  "1 x y" (x < y) — add the new interval (x, y) to the set of intervals. The length of the new interval is guaranteed to be strictly greater than all the previous intervals. "2 a b" (a ≠ b) — answer the question: is there a path from a-th (one-based) added interval to b-th (one-based) added interval? 

Answer all the queries. Note, that initially you have an empty set of intervals.


-----Input-----

The first line of the input contains integer n denoting the number of queries, (1 ≤ n ≤ 100). Each of the following lines contains a query as described above. All numbers in the input are integers and don't exceed 10^9 by their absolute value.

It's guaranteed that all queries are correct.


-----Output-----

For each query of the second type print "YES" or "NO" on a separate line depending on the answer.


-----Examples-----
Input
5
1 1 5
1 5 11
2 1 2
1 2 9
2 1 2

Output
NO
YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the world of Dota2, there are two parties: the Radiant and the Dire.



The Dota2 senate consists of senators coming from two parties. Now the senate wants to make a decision about a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:

Ban one senator's right: A senator can make another senator lose all his rights in this and all the following rounds.
Announce the victory: If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and make the decision about the change in the game.




Given a string representing each senator's party belonging. The character 'R' and 'D' represent the Radiant party and the Dire party respectively. Then if there are n senators, the size of the given string will be n.



The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.



Suppose every senator is smart enough and will play the best strategy for his own party, you need to predict which party will finally announce the victory and make the change in the Dota2 game. The output should be Radiant or Dire.


Example 1:

Input: "RD"
Output: "Radiant"
Explanation: The first senator comes from Radiant and he can just ban the next senator's right in the round 1. And the second senator can't exercise any rights any more since his right has been banned. And in the round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.




Example 2:

Input: "RDD"
Output: "Dire"
Explanation: 
The first senator comes from Radiant and he can just ban the next senator's right in the round 1. And the second senator can't exercise any rights anymore since his right has been banned. And the third senator comes from Dire and he can ban the first senator's right in the round 1. And in the round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.



Note:

The length of the given string will in the range [1, 10,000].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given are N pairwise distinct non-negative integers A_1,A_2,\ldots,A_N. Find the number of ways to choose a set of between 1 and K numbers (inclusive) from the given numbers so that the following two conditions are satisfied:

* The bitwise AND of the chosen numbers is S.
* The bitwise OR of the chosen numbers is T.

Constraints

* 1 \leq N \leq 50
* 1 \leq K \leq N
* 0 \leq A_i < 2^{18}
* 0 \leq S < 2^{18}
* 0 \leq T < 2^{18}
* A_i \neq A_j (1 \leq i < j \leq N)

Input

Input is given from Standard Input in the following format:


N K S T
A_1 A_2 ... A_N


Output

Print the answer.

Examples

Input

3 3 0 3
1 2 3


Output

2


Input

5 3 1 7
3 4 9 1 5


Output

2


Input

5 4 0 15
3 4 9 1 5


Output

3

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Anton likes permutations, especially he likes to permute their elements. Note that a permutation of *n* elements is a sequence of numbers {*a*1,<=*a*2,<=...,<=*a**n*}, in which every number from 1 to *n* appears exactly once.

One day Anton got a new permutation and started to play with it. He does the following operation *q* times: he takes two elements of the permutation and swaps these elements. After each operation he asks his friend Vanya, how many inversions there are in the new permutation. The number of inversions in a permutation is the number of distinct pairs (*i*,<=*j*) such that 1<=≤<=*i*<=&lt;<=*j*<=≤<=*n* and *a**i*<=&gt;<=*a**j*.

Vanya is tired of answering Anton's silly questions. So he asked you to write a program that would answer these questions instead of him.

Initially Anton's permutation was {1,<=2,<=...,<=*n*}, that is *a**i*<==<=*i* for all *i* such that 1<=≤<=*i*<=≤<=*n*.

Input Specification:
The first line of the input contains two integers *n* and *q* (1<=≤<=*n*<=≤<=200<=000,<=1<=≤<=*q*<=≤<=50<=000) — the length of the permutation and the number of operations that Anton does.

Each of the following *q* lines of the input contains two integers *l**i* and *r**i* (1<=≤<=*l**i*,<=*r**i*<=≤<=*n*) — the indices of elements that Anton swaps during the *i*-th operation. Note that indices of elements that Anton swaps during the *i*-th operation can coincide. Elements in the permutation are numbered starting with one.

Output Specification:
Output *q* lines. The *i*-th line of the output is the number of inversions in the Anton's permutation after the *i*-th operation.

Demo Input:
['5 4\n4 5\n2 4\n2 5\n2 2\n', '2 1\n2 1\n', '6 7\n1 4\n3 5\n2 3\n3 3\n3 6\n2 1\n5 1\n']

Demo Output:
['1\n4\n3\n3\n', '1\n', '5\n6\n7\n7\n10\n11\n8\n']

Note:
Consider the first sample.

After the first Anton's operation the permutation will be {1, 2, 3, 5, 4}. There is only one inversion in it: (4, 5).

After the second Anton's operation the permutation will be {1, 5, 3, 2, 4}. There are four inversions: (2, 3), (2, 4), (2, 5) and (3, 4).

After the third Anton's operation the permutation will be {1, 4, 3, 2, 5}. There are three inversions: (2, 3), (2, 4) and (3, 4).

After the fourth Anton's operation the permutation doesn't change, so there are still three inversions.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
At the legendary times of Nonsenso wars in ISM Dhanbad, there was a neck to neck competition between Barney Stinson and Sheldon Cooper. They both were on level 19. After trying too hard both of them could not decipher the nonsense, so they decided to play alongside. Sheldon Cooper had to pass a message to Barney Stinson. So he decided to convert each letter of the sentence to their corresponding to their ASCII codes. When Barney received the message he could not get anything. Now you have to design a code which converts the encrypted message to readable format.


Input
The input will consist of the first line containing the number of test cases ‘n’ followed by n lines of test cases.

Output

For each input print the decoded line.

Example

Input:
2
721011081081113287111114108100
871011089911110910132116111327311010010597


Output:
Hello World
Welcome to India

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

Time Limit: 4 seconds

Memory Limit: 256 megabytes

Problem Description:
Everyone knows that long ago on the territory of present-day Berland there lived Bindian tribes. Their capital was surrounded by *n* hills, forming a circle. On each hill there was a watchman, who watched the neighbourhood day and night.

In case of any danger the watchman could make a fire on the hill. One watchman could see the signal of another watchman, if on the circle arc connecting the two hills there was no hill higher than any of the two. As for any two hills there are two different circle arcs connecting them, the signal was seen if the above mentioned condition was satisfied on at least one of the arcs. For example, for any two neighbouring watchmen it is true that the signal of one will be seen by the other.

An important characteristics of this watch system was the amount of pairs of watchmen able to see each other's signals. You are to find this amount by the given heights of the hills.

Input Specification:
The first line of the input data contains an integer number *n* (3<=≤<=*n*<=≤<=106), *n* — the amount of hills around the capital. The second line contains *n* numbers — heights of the hills in clockwise order. All height numbers are integer and lie between 1 and 109.

Output Specification:
Print the required amount of pairs.

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

Demo Output:
['7\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little Alyona is celebrating Happy Birthday! Her mother has an array of *n* flowers. Each flower has some mood, the mood of *i*-th flower is *a**i*. The mood can be positive, zero or negative.

Let's define a subarray as a segment of consecutive flowers. The mother suggested some set of subarrays. Alyona wants to choose several of the subarrays suggested by her mother. After that, each of the flowers will add to the girl's happiness its mood multiplied by the number of chosen subarrays the flower is in.

For example, consider the case when the mother has 5 flowers, and their moods are equal to 1,<=<=-<=2,<=1,<=3,<=<=-<=4. Suppose the mother suggested subarrays (1,<=<=-<=2), (3,<=<=-<=4), (1,<=3), (1,<=<=-<=2,<=1,<=3). Then if the girl chooses the third and the fourth subarrays then: 
 -  the first flower adds 1·1<==<=1 to the girl's happiness, because he is in one of chosen subarrays, -  the second flower adds (<=-<=2)·1<==<=<=-<=2, because he is in one of chosen subarrays, -  the third flower adds 1·2<==<=2, because he is in two of chosen subarrays, -  the fourth flower adds 3·2<==<=6, because he is in two of chosen subarrays, -  the fifth flower adds (<=-<=4)·0<==<=0, because he is in no chosen subarrays. 
Thus, in total 1<=+<=(<=-<=2)<=+<=2<=+<=6<=+<=0<==<=7 is added to the girl's happiness. Alyona wants to choose such subarrays from those suggested by the mother that the value added to her happiness would be as large as possible. Help her do this!

Alyona can choose any number of the subarrays, even 0 or all suggested by her mother.

Input Specification:
The first line contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=100) — the number of flowers and the number of subarrays suggested by the mother.

The second line contains the flowers moods — *n* integers *a*1,<=*a*2,<=...,<=*a**n* (<=-<=100<=≤<=*a**i*<=≤<=100).

The next *m* lines contain the description of the subarrays suggested by the mother. The *i*-th of these lines contain two integers *l**i* and *r**i* (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=*n*) denoting the subarray *a*[*l**i*],<=*a*[*l**i*<=+<=1],<=...,<=*a*[*r**i*].

Each subarray can encounter more than once.

Output Specification:
Print single integer — the maximum possible value added to the Alyona's happiness.

Demo Input:
['5 4\n1 -2 1 3 -4\n1 2\n4 5\n3 4\n1 4\n', '4 3\n1 2 3 4\n1 3\n2 4\n1 1\n', '2 2\n-1 -2\n1 1\n1 2\n']

Demo Output:
['7\n', '16\n', '0\n']

Note:
The first example is the situation described in the statements.

In the second example Alyona should choose all subarrays.

The third example has answer 0 because Alyona can choose none of the subarrays.

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