vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Ralph is in the Binary Country. The Binary Country consists of n cities and (n - 1) bidirectional roads connecting the cities. The roads are numbered from 1 to (n - 1), the i-th road connects the city labeled <image> (here ⌊ x⌋ denotes the x rounded down to the nearest integer) and the city labeled (i + 1), and the length of the i-th road is Li.

Now Ralph gives you m queries. In each query he tells you some city Ai and an integer Hi. He wants to make some tours starting from this city. He can choose any city in the Binary Country (including Ai) as the terminal city for a tour. He gains happiness (Hi - L) during a tour, where L is the distance between the city Ai and the terminal city.

Ralph is interested in tours from Ai in which he can gain positive happiness. For each query, compute the sum of happiness gains for all such tours.

Ralph will never take the same tour twice or more (in one query), he will never pass the same city twice or more in one tour.

Input

The first line contains two integers n and m (1 ≤ n ≤ 106, 1 ≤ m ≤ 105).

(n - 1) lines follow, each line contains one integer Li (1 ≤ Li ≤ 105), which denotes the length of the i-th road.

m lines follow, each line contains two integers Ai and Hi (1 ≤ Ai ≤ n, 0 ≤ Hi ≤ 107).

Output

Print m lines, on the i-th line print one integer — the answer for the i-th query.

Examples

Input

2 2
5
1 8
2 4


Output

11
4


Input

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


Output

11
6
3
28

Note

Here is the explanation for the second sample.

Ralph's first query is to start tours from city 2 and Hi equals to 4. Here are the options:

  * He can choose city 5 as his terminal city. Since the distance between city 5 and city 2 is 3, he can gain happiness 4 - 3 = 1. 
  * He can choose city 4 as his terminal city and gain happiness 3. 
  * He can choose city 1 as his terminal city and gain happiness 2. 
  * He can choose city 3 as his terminal city and gain happiness 1. 
  * Note that Ralph can choose city 2 as his terminal city and gain happiness 4. 
  * Ralph won't choose city 6 as his terminal city because the distance between city 6 and city 2 is 5, which leads to negative happiness for Ralph. 



So the answer for the first query is 1 + 3 + 2 + 1 + 4 = 11.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
In this problem, your task is to use ASCII graphics to paint a cardiogram. 

A cardiogram is a polyline with the following corners:

That is, a cardiogram is fully defined by a sequence of positive integers *a*1,<=*a*2,<=...,<=*a**n*.

Your task is to paint a cardiogram by given sequence *a**i*.

Input Specification:
The first line contains integer *n* (2<=≤<=*n*<=≤<=1000). The next line contains the sequence of integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=1000). It is guaranteed that the sum of all *a**i* doesn't exceed 1000.

Output Specification:
Print *max* |*y**i*<=-<=*y**j*| lines (where *y**k* is the *y* coordinate of the *k*-th point of the polyline), in each line print  characters. Each character must equal either «<=/<=» (slash), « \ » (backslash), « » (space). The printed image must be the image of the given polyline. Please study the test samples for better understanding of how to print a cardiogram.

Note that in this problem the checker checks your answer taking spaces into consideration. Do not print any extra characters. Remember that the wrong answer to the first pretest doesn't give you a penalty.

Demo Input:
['5\n3 1 2 5 1\n', '3\n1 5 1\n']

Demo Output:
['/\u2009\\     \n  \u2009/\u2009\\\u2009/\u2009  \\    \n \u2009/\u2009      \\   \n\u2009/\u2009        \\  \n          \\\u2009/\u2009\n', '/\u2009\\     \n  \\    \n   \\   \n    \\  \n     \\\u2009/\u2009\n']

Note:
Due to the technical reasons the answers for the samples cannot be copied from the statement. We've attached two text documents with the answers below.

http://assets.codeforces.com/rounds/435/1.txt

http://assets.codeforces.com/rounds/435/2.txt

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a deck of $n$ cards. The $i$-th card has a number $a_i$ on the front and a number $b_i$ on the back. Every integer between $1$ and $2n$ appears exactly once on the cards.

A deck is called sorted if the front values are in increasing order and the back values are in decreasing order. That is, if $a_i< a_{i+1}$ and $b_i> b_{i+1}$ for all $1\le i<n$.

To flip a card $i$ means swapping the values of $a_i$ and $b_i$. You must flip some subset of cards (possibly, none), then put all the cards in any order you like. What is the minimum number of cards you must flip in order to sort the deck?


-----Input-----

The first line contains a single integer $n$ ($1\le n\le 2\cdot 10^5$) — the number of cards.

The next $n$ lines describe the cards. The $i$-th of these lines contains two integers $a_i, b_i$ ($1\le a_i, b_i\le 2n$). Every integer between $1$ and $2n$ appears exactly once.


-----Output-----

If it is impossible to sort the deck, output "-1". Otherwise, output the minimum number of flips required to sort the deck.


-----Examples-----

Input
5
3 10
6 4
1 9
5 8
2 7
Output
2
Input
2
1 2
3 4
Output
-1
Input
3
1 2
3 6
4 5
Output
-1


-----Note-----

In the first test case, we flip the cards $(1, 9)$ and $(2, 7)$. The deck is then ordered $(3,10), (5,8), (6,4), (7,2), (9,1)$. It is sorted because $3<5<6<7<9$ and $10>8>4>2>1$.

In the second test case, it is impossible to sort the deck.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Iahub likes chess very much. He even invented a new chess piece named Coder. A Coder can move (and attack) one square horizontally or vertically. More precisely, if the Coder is located at position (*x*,<=*y*), he can move to (or attack) positions (*x*<=+<=1,<=*y*), (*x*–1,<=*y*), (*x*,<=*y*<=+<=1) and (*x*,<=*y*–1).

Iahub wants to know how many Coders can be placed on an *n*<=×<=*n* chessboard, so that no Coder attacks any other Coder.

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=1000).

Output Specification:
On the first line print an integer, the maximum number of Coders that can be placed on the chessboard.

On each of the next *n* lines print *n* characters, describing the configuration of the Coders. For an empty cell print an '.', and for a Coder print a 'C'.

If there are multiple correct answers, you can print any.

Demo Input:
['2\n']

Demo Output:
['2\nC.\n.C\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
N ants are in a circular race. The length of the race is 1000 meters and ant number i is initially Vi meters far from starting point (point 0) of the race in clockwise order. All the ants walk with a speed of 0.1 meters per second, some of them walk in clockwise order, some in counter clockwise order. When two ants meet at a point, they say "Hi" to each other and both of them change their direction of walking to the opposite direction. This process is timeless, meaning they say "Hi" and change their direction in 0 seconds.

You are given the initial position of ants, you don't know their initial directions but you want to know how many times do they say "Hi" to each other after 1000000006 ( 10^9+6 seconds ). You need to find the initial walking direction of ants such that, c1+c2+c3+...+cn is maximized, where ci is the number of times ant number i say "Hi". Print this maximum value.

Input: 

The first line of the input contains an integer N, the number of ants. N is not greater than 100. 

Next line contains n numbers V1 , V2 , ... , VN. All Vi are non negative integers less than 1000. All Vi are distinct.

Output: 

On the only line of the output print an integer being the answer to the test.

Sample Input 

2 

0 500

Sample Output 

400000

Explanation 

In the example there are two ants, In case their direction is the same, they will never say hi to each other, in the other case they will say "Hi" to each other in times 2500, 7500,12500, ... , 999999750. so the result for an Ant would be (999997500 - 2500)/5000+1 = 200000. Hence the answer is 200000*2 = 400000.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Define the simple skewness of a collection of numbers to be the collection's mean minus its median. You are given a list of n (not necessarily distinct) integers. Find the non-empty subset (with repetition) with the maximum simple skewness.

The mean of a collection is the average of its elements. The median of a collection is its middle element when all of its elements are sorted, or the average of its two middle elements if it has even size.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of elements in the list.

The second line contains n integers xi (0 ≤ xi ≤ 1 000 000) — the ith element of the list.

Output

In the first line, print a single integer k — the size of the subset.

In the second line, print k integers — the elements of the subset in any order.

If there are multiple optimal subsets, print any.

Examples

Input

4
1 2 3 12


Output

3
1 2 12 


Input

4
1 1 2 2


Output

3
1 1 2 


Input

2
1 2


Output

2
1 2

Note

In the first case, the optimal subset is <image>, which has mean 5, median 2, and simple skewness of 5 - 2 = 3.

In the second case, the optimal subset is <image>. Note that repetition is allowed.

In the last case, any subset has the same median and mean, so all have simple skewness of 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It was the third month of remote learning, Nastya got sick of staying at dormitory, so she decided to return to her hometown. In order to make her trip more entertaining, one of Nastya's friend presented her an integer array $a$.

Several hours after starting her journey home Nastya remembered about the present. To entertain herself she decided to check, are there four different indices $x, y, z, w$ such that $a_x + a_y = a_z + a_w$.

Her train has already arrived the destination, but she still hasn't found the answer. Can you help her unravel the mystery?


-----Input-----

The first line contains the single integer $n$ ($4 \leq n \leq 200000$) — the size of the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 2.5 \cdot 10^6$).


-----Output-----

Print "YES" if there are such four indices, and "NO" otherwise.

If such indices exist, print these indices $x$, $y$, $z$ and $w$ ($1 \le x, y, z, w \le n$).

If there are multiple answers, print any of them.


-----Examples-----

Input
6
2 1 5 2 7 4
Output
YES
2 3 1 6
Input
5
1 3 1 9 20
Output
NO


-----Note-----

In the first example $a_2 + a_3 = 1 + 5 = 2 + 4 = a_1 + a_6$. Note that there are other answer, for example, 2 3 4 6.

In the second example, we can't choose four indices. The answer 1 2 2 3 is wrong, because indices should be different, despite that $a_1 + a_2 = 1 + 3 = 3 + 1 = a_2 + a_3$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today is Chef's birthday. His mom has surprised him with truly fruity gifts: 2 fruit baskets. The first basket contains N apples, and the second one contains M oranges. Chef likes apples and oranges very much but he likes them equally, and therefore, wants to have the minimum possible difference between the number of apples and oranges he has. To do so, he can purchase 1 apple or 1 orange by paying exactly 1 gold coin (that's some expensive fruit, eh?). Chef can purchase fruits at most K times (as he has only K gold coins in his pocket) to make the difference the minimum possible.
Our little Chef is busy in celebrating his birthday to the fullest, and therefore, he has handed this job to his best friend — you. Can you help him by finding the minimum possible difference he can achieve between the number of apples and orange he owns?

-----Input-----
The first line of input contains a single integer T denoting the number of test cases. The first and only line of each test case contains 3 space separated integers — N, M and K — denoting the number of apples, number of oranges, and number of gold coins our little Chef has.

-----Output-----
For each test case, output the minimum possible difference between the number of apples and oranges that Chef can achieve.

-----Constraints-----
- 1 ≤ T ≤ 100
- 1 ≤ N, M, K ≤ 100

-----Example-----Input
3
3 4 1
5 2 1
3 4 3

Output
0
2
0

-----Explanation-----
- Test 1: Chef will buy 1 apple by paying 1 gold coin and will have equal number of apples and oranges. 
- Test 2: Chef will buy 1 orange by paying 1 gold coin and will have 5 apples and 3 oranges.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a grass field that stretches infinitely.
In this field, there is a negligibly small cow. Let (x, y) denote the point that is x\ \mathrm{cm} south and y\ \mathrm{cm} east of the point where the cow stands now. The cow itself is standing at (0, 0).
There are also N north-south lines and M east-west lines drawn on the field. The i-th north-south line is the segment connecting the points (A_i, C_i) and (B_i, C_i), and the j-th east-west line is the segment connecting the points (D_j, E_j) and (D_j, F_j).
What is the area of the region the cow can reach when it can move around as long as it does not cross the segments (including the endpoints)? If this area is infinite, print INF instead.

-----Constraints-----
 - All values in input are integers between -10^9 and 10^9  (inclusive).
 - 1 \leq N, M \leq 1000
 - A_i < B_i\ (1 \leq i \leq N)
 - E_j < F_j\ (1 \leq j \leq M)
 - The point (0, 0) does not lie on any of the given segments.

-----Input-----
Input is given from Standard Input in the following format:
N M
A_1 B_1 C_1
:
A_N B_N C_N
D_1 E_1 F_1
:
D_M E_M F_M

-----Output-----
If the area of the region the cow can reach is infinite, print INF; otherwise, print an integer representing the area in \mathrm{cm^2}.
(Under the constraints, it can be proved that the area of the region is always an integer if it is not infinite.)

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

-----Sample Output-----
13

The area of the region the cow can reach is 13\ \mathrm{cm^2}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are the judge at a competitive eating competition and you need to choose a winner!

There are three foods at the competition and each type of food is worth a different amount of points.
Points are as follows:

- Chickenwings: 5 points  

- Hamburgers: 3 points   

- Hotdogs: 2 points

Write a function that helps you create a scoreboard. 
It takes as a parameter a list of objects representing the participants, for example:
```
[
  {name: "Habanero Hillary", chickenwings: 5 , hamburgers: 17, hotdogs: 11},
  {name: "Big Bob" , chickenwings: 20, hamburgers: 4, hotdogs: 11}
]
```
It should return 
"name" and "score" properties sorted by score; if scores are equals, sort alphabetically by name.
```
[
  {name: "Big Bob", score: 134},
  {name: "Habanero Hillary", score: 98}
]
```
Happy judging!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is currently facing the north direction. Each second he rotates exactly 90 degrees in clockwise direction. Find the direction in which Chef is facing after exactly X seconds.

\textbf{Note}: There are only 4 directions: North, East, South, West (in clockwise order).

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

- First line will contain T, number of testcases. Then the testcases follow.
- Each testcase contains of a single integer X.

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

For each testcase, output the direction in which Chef is facing after exactly X seconds.

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

$1 ≤ T ≤ 100$
$1 ≤ X ≤ 1000$

----- Sample Input 1 ------ 
3
1
3
6

----- Sample Output 1 ------ 
East
West
South

----- explanation 1 ------ 
Chef is facing North in the starting.

Test Case $1$: After $1$ second he turns $90$ degrees clockwise and now faces the east direction.

Test Case $2$:
Direction after $1$ second- east

Direction after $2$ seconds- south

Direction after $3$ seconds- west

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
We'll call an array of *n* non-negative integers *a*[1],<=*a*[2],<=...,<=*a*[*n*] interesting, if it meets *m* constraints. The *i*-th of the *m* constraints consists of three integers *l**i*, *r**i*, *q**i* (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=*n*) meaning that value  should be equal to *q**i*. 

Your task is to find any interesting array of *n* elements or state that such array doesn't exist.

Expression *x*&amp;*y* means the bitwise AND of numbers *x* and *y*. In programming languages C++, Java and Python this operation is represented as "&amp;", in Pascal — as "and".

Input Specification:
The first line contains two integers *n*, *m* (1<=≤<=*n*<=≤<=105, 1<=≤<=*m*<=≤<=105) — the number of elements in the array and the number of limits.

Each of the next *m* lines contains three integers *l**i*, *r**i*, *q**i* (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=*n*, 0<=≤<=*q**i*<=&lt;<=230) describing the *i*-th limit.

Output Specification:
If the interesting array exists, in the first line print "YES" (without the quotes) and in the second line print *n* integers *a*[1],<=*a*[2],<=...,<=*a*[*n*] (0<=≤<=*a*[*i*]<=&lt;<=230) decribing the interesting array. If there are multiple answers, print any of them.

If the interesting array doesn't exist, print "NO" (without the quotes) in the single line.

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

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an n × m rectangular table consisting of lower case English letters. In one operation you can completely remove one column from the table. The remaining parts are combined forming a new table. For example, after removing the second column from the table

abcd

edfg

hijk



 

we obtain the table:

acd

efg

hjk



 

A table is called good if its rows are ordered from top to bottom lexicographically, i.e. each row is lexicographically no larger than the following one. Determine the minimum number of operations of removing a column needed to make a given table good.


-----Input-----

The first line contains two integers  — n and m (1 ≤ n, m ≤ 100).

Next n lines contain m small English letters each — the characters of the table.


-----Output-----

Print a single number — the minimum number of columns that you need to remove in order to make the table good.


-----Examples-----
Input
1 10
codeforces

Output
0

Input
4 4
case
care
test
code

Output
2

Input
5 4
code
forc
esco
defo
rces

Output
4



-----Note-----

In the first sample the table is already good.

In the second sample you may remove the first and third column.

In the third sample you have to remove all the columns (note that the table where all rows are empty is considered good by definition).

Let strings s and t have equal length. Then, s is lexicographically larger than t if they are not equal and the character following the largest common prefix of s and t (the prefix may be empty) in s is alphabetically larger than the corresponding character of t.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the year 2168, AtCoder Inc., which is much larger than now, is starting a limited express train service called AtCoder Express.
In the plan developed by the president Takahashi, the trains will run as follows:
 - A train will run for (t_1 + t_2 + t_3 + ... + t_N) seconds.
 - In the first t_1 seconds, a train must run at a speed of at most v_1 m/s (meters per second). Similarly, in the subsequent t_2 seconds, a train must run at a speed of at most v_2 m/s, and so on.
According to the specifications of the trains, the acceleration of a train must be always within ±1m/s^2. Additionally, a train must stop at the beginning and the end of the run.
Find the maximum possible distance that a train can cover in the run.

-----Constraints-----
 - 1 \leq N \leq 100
 - 1 \leq t_i \leq 200
 - 1 \leq v_i \leq 100
 - All input values are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
t_1 t_2 t_3 … t_N
v_1 v_2 v_3 … v_N

-----Output-----
Print the maximum possible that a train can cover in the run.

Output is considered correct if its absolute difference from the judge's output is at most 10^{-3}.

-----Sample Input-----
1
100
30

-----Sample Output-----
2100.000000000000000


The maximum distance is achieved when a train runs as follows:
 - In the first 30 seconds, it accelerates at a rate of 1m/s^2, covering 450 meters.
 - In the subsequent 40 seconds, it maintains the velocity of 30m/s, covering 1200 meters.
 - In the last 30 seconds, it decelerates at the acceleration of -1m/s^2, covering 450 meters.
The total distance covered is 450 + 1200 + 450 = 2100 meters.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a fair coin and two integers X and N.

You repeatedly flip the coin and perform the following operation based on the result:
If it lands on heads, then X will increase by 1. However, if X = N then X will not change.
If it lands on tails, X will decrease by 1.

You stop as soon as the value of X becomes 1.

Find the expected number of coin flips.

Note that it is guaranteed that under the given constraints, the answer is an integer and does not exceed 2 \cdot 10^{18}

------ 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 space separated integers X and N.

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

For each testcase, output the expected number of coin flips.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ X ≤ N ≤ 10^{9}$

----- Sample Input 1 ------ 
4
1 3
2 2
12 12
568 57800
----- Sample Output 1 ------ 
0
2
132
65223144

----- explanation 1 ------ 
In the first test case, $X$ is already $1$. So, the expected number of coin flip in this case is $0$.

In the second test case, if the coin lands on head, $X$ will not change because $X$ is equal to $N$ here. Whenever the coin lands on tail, $X$ will decrease by $1$ and the game ends as $X$ becomes $1$. The expected number of coin flips to get the first tail is $2$. So, the answer for the case is $2$.

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