vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The little girl loves the problems on array queries very much.

One day she came across a rather well-known problem: you've got an array of n elements (the elements of the array are indexed starting from 1); also, there are q queries, each one is defined by a pair of integers l_{i}, r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n). You need to find for each query the sum of elements of the array with indexes from l_{i} to r_{i}, inclusive.

The little girl found the problem rather boring. She decided to reorder the array elements before replying to the queries in a way that makes the sum of query replies maximum possible. Your task is to find the value of this maximum sum.


-----Input-----

The first line contains two space-separated integers n (1 ≤ n ≤ 2·10^5) and q (1 ≤ q ≤ 2·10^5) — the number of elements in the array and the number of queries, correspondingly.

The next line contains n space-separated integers a_{i} (1 ≤ a_{i} ≤ 2·10^5) — the array elements.

Each of the following q lines contains two space-separated integers l_{i} and r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n) — the i-th query.


-----Output-----

In a single line print a single integer — the maximum sum of query replies after the array elements are reordered.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.


-----Examples-----
Input
3 3
5 3 2
1 2
2 3
1 3

Output
25

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

Output
33

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a set Y of n distinct positive integers y1, y2, ..., yn.

Set X of n distinct positive integers x1, x2, ..., xn is said to generate set Y if one can transform X to Y by applying some number of the following two operation to integers in X:

  1. Take any integer xi and multiply it by two, i.e. replace xi with 2·xi. 
  2. Take any integer xi, multiply it by two and add one, i.e. replace xi with 2·xi + 1. 



Note that integers in X are not required to be distinct after each operation.

Two sets of distinct integers X and Y are equal if they are equal as sets. In other words, if we write elements of the sets in the array in the increasing order, these arrays would be equal.

Note, that any set of integers (or its permutation) generates itself.

You are given a set Y and have to find a set X that generates Y and the maximum element of X is mininum possible.

Input

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

The second line contains n integers y1, ..., yn (1 ≤ yi ≤ 109), that are guaranteed to be distinct.

Output

Print n integers — set of distinct integers that generate Y and the maximum element of which is minimum possible. If there are several such sets, print any of them.

Examples

Input

5
1 2 3 4 5


Output

4 5 2 3 1 


Input

6
15 14 3 13 1 12


Output

12 13 14 7 3 1 


Input

6
9 7 13 17 5 11


Output

4 5 2 6 3 1 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It was recycling day in Kekoland. To celebrate it Adil and Bera went to Central Perk where they can take bottles from the ground and put them into a recycling bin.

We can think Central Perk as coordinate plane. There are n bottles on the ground, the i-th bottle is located at position (x_{i}, y_{i}). Both Adil and Bera can carry only one bottle at once each. 

For both Adil and Bera the process looks as follows:   Choose to stop or to continue to collect bottles.  If the choice was to continue then choose some bottle and walk towards it.  Pick this bottle and walk to the recycling bin.  Go to step 1. 

Adil and Bera may move independently. They are allowed to pick bottles simultaneously, all bottles may be picked by any of the two, it's allowed that one of them stays still while the other one continues to pick bottles.

They want to organize the process such that the total distance they walk (the sum of distance walked by Adil and distance walked by Bera) is minimum possible. Of course, at the end all bottles should lie in the recycling bin.


-----Input-----

First line of the input contains six integers a_{x}, a_{y}, b_{x}, b_{y}, t_{x} and t_{y} (0 ≤ a_{x}, a_{y}, b_{x}, b_{y}, t_{x}, t_{y} ≤ 10^9) — initial positions of Adil, Bera and recycling bin respectively.

The second line contains a single integer n (1 ≤ n ≤ 100 000) — the number of bottles on the ground.

Then follow n lines, each of them contains two integers x_{i} and y_{i} (0 ≤ x_{i}, y_{i} ≤ 10^9) — position of the i-th bottle.

It's guaranteed that positions of Adil, Bera, recycling bin and all bottles are distinct.


-----Output-----

Print one real number — the minimum possible total distance Adil and Bera need to walk in order to put all bottles into recycling bin. Your answer will be considered correct if its absolute or relative error does not exceed 10^{ - 6}.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct if $\frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-6}$.


-----Examples-----
Input
3 1 1 2 0 0
3
1 1
2 1
2 3

Output
11.084259940083

Input
5 0 4 2 2 0
5
5 2
3 0
5 5
3 5
3 3

Output
33.121375178000



-----Note-----

Consider the first sample.

Adil will use the following path: $(3,1) \rightarrow(2,1) \rightarrow(0,0) \rightarrow(1,1) \rightarrow(0,0)$.

Bera will use the following path: $(1,2) \rightarrow(2,3) \rightarrow(0,0)$.

Adil's path will be $1 + \sqrt{5} + \sqrt{2} + \sqrt{2}$ units long, while Bera's path will be $\sqrt{2} + \sqrt{13}$ units long.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
On a table are N cards, with a positive integer printed on the front and back of each card (possibly different).
We flip any number of cards, and after we choose one card. 
If the number X on the back of the chosen card is not on the front of any card, then this number X is good.
What is the smallest number that is good?  If no number is good, output 0.
Here, fronts[i] and backs[i] represent the number on the front and back of card i. 
A flip swaps the front and back numbers, so the value on the front is now on the back and vice versa.
Example:
Input: fronts = [1,2,4,4,7], backs = [1,3,4,1,3]
Output: 2
Explanation: If we flip the second card, the fronts are [1,3,4,4,7] and the backs are [1,2,4,1,3].
We choose the second card, which has number 2 on the back, and it isn't on the front of any card, so 2 is good.
 
Note:

1 <= fronts.length == backs.length <= 1000.
1 <= fronts[i] <= 2000.
1 <= backs[i] <= 2000.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Shaass has decided to hunt some birds. There are n horizontal electricity wires aligned parallel to each other. Wires are numbered 1 to n from top to bottom. On each wire there are some oskols sitting next to each other. Oskol is the name of a delicious kind of birds in Shaass's territory. Supposed there are a_{i} oskols sitting on the i-th wire. $40$ 

Sometimes Shaass shots one of the birds and the bird dies (suppose that this bird sat at the i-th wire). Consequently all the birds on the i-th wire to the left of the dead bird get scared and jump up on the wire number i - 1, if there exists no upper wire they fly away. Also all the birds to the right of the dead bird jump down on wire number i + 1, if there exists no such wire they fly away. 

Shaass has shot m birds. You're given the initial number of birds on each wire, tell him how many birds are sitting on each wire after the shots.


-----Input-----

The first line of the input contains an integer n, (1 ≤ n ≤ 100). The next line contains a list of space-separated integers a_1, a_2, ..., a_{n}, (0 ≤ a_{i} ≤ 100). 

The third line contains an integer m, (0 ≤ m ≤ 100). Each of the next m lines contains two integers x_{i} and y_{i}. The integers mean that for the i-th time Shaass shoot the y_{i}-th (from left) bird on the x_{i}-th wire, (1 ≤ x_{i} ≤ n, 1 ≤ y_{i}). It's guaranteed there will be at least y_{i} birds on the x_{i}-th wire at that moment.


-----Output-----

On the i-th line of the output print the number of birds on the i-th wire.


-----Examples-----
Input
5
10 10 10 10 10
5
2 5
3 13
2 12
1 13
4 6

Output
0
12
5
0
16

Input
3
2 4 1
1
2 2

Output
3
0
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A maze is represented by a tree (an undirected graph, where exactly one way exists between each pair of vertices). In the maze the entrance vertex and the exit vertex are chosen with some probability. The exit from the maze is sought by Deep First Search. If there are several possible ways to move, the move is chosen equiprobably. Consider the following pseudo-code:
    
    
      
    DFS(x)  
        if x == exit vertex then  
            finish search  
        flag[x] <- TRUE  
        random shuffle the vertices' order in V(x) // here all permutations have equal probability to be chosen  
        for i <- 1 to length[V] do  
            if flag[V[i]] = FALSE then  
                count++;  
                DFS(y);  
        count++;  
    

V(x) is the list vertices adjacent to x. The flag array is initially filled as FALSE. DFS initially starts with a parameter of an entrance vertex. When the search is finished, variable count will contain the number of moves.

Your task is to count the mathematical expectation of the number of moves one has to do to exit the maze.

Input

The first line determines the number of vertices in the graph n (1 ≤ n ≤ 105). The next n - 1 lines contain pairs of integers ai and bi, which show the existence of an edge between ai and bi vertices (1 ≤ ai, bi ≤ n). It is guaranteed that the given graph is a tree.

Next n lines contain pairs of non-negative numbers xi and yi, which represent the probability of choosing the i-th vertex as an entrance and exit correspondingly. The probabilities to choose vertex i as an entrance and an exit equal <image> and <image> correspondingly. The sum of all xi and the sum of all yi are positive and do not exceed 106.

Output

Print the expectation of the number of moves. The absolute or relative error should not exceed 10 - 9.

Examples

Input

2
1 2
0 1
1 0


Output

1.00000000000000000000


Input

3
1 2
1 3
1 0
0 2
0 3


Output

2.00000000000000000000


Input

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


Output

4.04081632653

Note

In the first sample the entrance vertex is always 1 and the exit vertex is always 2.

In the second sample the entrance vertex is always 1 and the exit vertex with the probability of 2/5 will be 2 of with the probability if 3/5 will be 3. The mathematical expectations for the exit vertices 2 and 3 will be equal (symmetrical cases). During the first move one can go to the exit vertex with the probability of 0.5 or to go to a vertex that's not the exit vertex with the probability of 0.5. In the first case the number of moves equals 1, in the second one it equals 3. The total mathematical expectation is counted as 2 / 5 × (1 × 0.5 + 3 × 0.5) + 3 / 5 × (1 × 0.5 + 3 × 0.5)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You love array, don't you?

You are given two integer N and M, along with an array B of length N containing pairwise distinct integers. You have to find the number of array A of length N satisfying the follow conditions:

1. 1 ≤ A_{i} ≤ M.
2. A_{i} \neq A_{j} for all 1 ≤ i < j ≤ N.
3. A_{i} \neq B_{i} for all 1 ≤ i ≤ N.

Since the answer can be very large, output it under modulo 10^{9} + 7.

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

- The first line of the input contains two space-separated integers N and M.
- The second line of the input contains N separated integers B_{1}, B_{2}, \dots, B_{N} - the array B.

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

Output on a single line the number of satisfactory array modulo 10^{9} + 7.

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

$1 ≤ N ≤ 2 \cdot 10^{5}$
$1 ≤ M ≤ 3 \cdot 10^{5}$
$1 ≤ B_{i} ≤ 10^{9}$
$B_{i} \neq B_{j}$ for all $1 ≤i < j ≤N$.

------ subtasks ------ 

Subtask $1$ (30 points): $1 ≤ R ≤ 10\,000$
Subtask $2$ (70 points): $1 ≤ R ≤ 10^{9}$

----- Sample Input 1 ------ 
3 4
5 1 2
----- Sample Output 1 ------ 
14
----- explanation 1 ------ 
All satisfactory arrays are:
- $[1, 2, 3]$
- $[2, 3, 1]$
- $[3, 2, 1]$
- $[1, 2, 4]$
- $[2, 4, 1]$
- $[4, 2, 1]$
- $[1, 3, 4]$
- $[1, 4, 3]$
- $[3, 4, 1]$
- $[4, 3, 1]$
- $[2, 3, 4]$
- $[2, 4, 3]$
- $[3, 2, 4]$
- $[4, 2, 3]$

----- Sample Input 2 ------ 
2 2
1 3
----- Sample Output 2 ------ 
1
----- explanation 2 ------ 
The only satisfactory array is:
- $[2, 1]$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an $r\! \times \! c$ grid. Each cell of this grid is filled with a number between $1$ and $r{\cdot }c$ inclusive, and each cell’s number is distinct.

Define a grid of numbers to be monotonic if each row and column is either increasing or decreasing (this can be different for each row or column).

Define a subgrid of the grid as follows: First choose some nonempty subset of the rows and columns. Next, take elements that lie in both the chosen rows and columns in the same order.

There are $(2^r{-}1)(2^c{-}1)$ nonempty subgrids of the given grid. Of these subgrids, count how many are monotonic.

Consider this grid:$1$  $2$  $5$

$7$  $6$  $4$

$9$  $8$  $3$


There are nine $1{\times }1$ subgrids, nine $1{\times }2$’s, three $1{\times }3$’s, nine $2{\times }1$’s, nine $2{\times }2$’s, three $2{\times }3$’s, three $3{\times }1$’s, three $3{\times }2$’s, and one $3{\times }3$. They are all monotonic, for $9{+}9{+}3{+}9{+}9{+}3{+}3{+}3{+}1=49$ monotonic subgrids.

-----Input-----
Each test case will begin with a line with two space-separated integers $r$ and $c$ ($1\! \le \! r,c\! \le \! 20$), which are the dimensions of the grid.

Each of the next $r$ lines will contain $c$ space-separated integers $x$ ($1\! \le \! x\! \le \! r{\cdot }c$, all $x$’s are unique). This is the grid.

-----Output-----
Output a single integer, which is the number of monotonic subgrids in the given grid.

-----Examples-----
Sample Input:
3 3
1 2 5
7 6 4
9 8 3
Sample Output:
49

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given *n* strings *s*1,<=*s*2,<=...,<=*s**n* consisting of characters 0 and 1. *m* operations are performed, on each of them you concatenate two existing strings into a new one. On the *i*-th operation the concatenation *s**a**i**s**b**i* is saved into a new string *s**n*<=+<=*i* (the operations are numbered starting from 1). After each operation you need to find the maximum positive integer *k* such that all possible strings consisting of 0 and 1 of length *k* (there are 2*k* such strings) are substrings of the new string. If there is no such *k*, print 0.

Input Specification:
The first line contains single integer *n* (1<=≤<=*n*<=≤<=100) — the number of strings. The next *n* lines contain strings *s*1,<=*s*2,<=...,<=*s**n* (1<=≤<=|*s**i*|<=≤<=100), one per line. The total length of strings is not greater than 100.

The next line contains single integer *m* (1<=≤<=*m*<=≤<=100) — the number of operations. *m* lines follow, each of them contains two integers *a**i* abd *b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*<=+<=*i*<=-<=1) — the number of strings that are concatenated to form *s**n*<=+<=*i*.

Output Specification:
Print *m* lines, each should contain one integer — the answer to the question after the corresponding operation.

Demo Input:
['5\n01\n10\n101\n11111\n0\n3\n1 2\n6 5\n4 4\n']

Demo Output:
['1\n2\n0\n']

Note:
On the first operation, a new string "0110" is created. For *k* = 1 the two possible binary strings of length *k* are "0" and "1", they are substrings of the new string. For *k* = 2 and greater there exist strings of length *k* that do not appear in this string (for *k* = 2 such string is "00"). So the answer is 1.

On the second operation the string "01100" is created. Now all strings of length *k* = 2 are present.

On the third operation the string "1111111111" is created. There is no zero, so the answer is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef's younger brother is in town. He's a big football fan and has a very important match to watch tonight. But the Chef wants to watch the season finale of MasterChef which will be aired at the same time. Now they don't want to fight over it like they used to when they were little kids. They want to decide it in a fair way. So they agree to play a game to make a decision. Their favourite childhood game!
The game consists of C boards. Each board i is a grid of dimension ni x mi.
Rules of the game:

- A coin is placed at (1,1) on every board initially.

- Each one takes a turn alternatively.

- In one turn, a player can choose any one board and move a coin from a cell (i,j) to one of the following cells:

	(i+1,j) OR (i+2,j) OR (i,j+1) OR (i,j+2) OR (i+1,j+1) OR (i+2,j+2).

- A coin cannot be moved out of the board at any point during the game.

- A coin cannot be moved once it reaches the cell (n,m) where n and m are the dimensions of the board of that coin.

- A player MUST make one valid move.

- The player who makes the last move gets to watch TV. 

Both of them are passionate about their interests and want to watch their respective shows. So they will obviously make optimal moves in every turn. The Chef, being the elder brother, takes the first turn.
Your task is to predict which show they will be watching tonight.

-----Input:-----
The first line of input contains a single integer T, the number of test cases. T tests follow.Each test case starts with a single line containing C, the number of boards in the game.
Then follow C lines: each containing 2 integers ni and mi, the dimensions of the ith board.

-----Output:-----
Given the number and dimensions of boards, for each test case, output in a single line: "MasterChef" if the Chef wins or "Football" if his brother wins.

-----Constraints:-----

1<=T<=10000

1<=C<=20

2<=ni,mi<=1000

-----Example:-----Input:

1

1

2 2

Output:

MasterChef

Explanation: 

The Chef can move the coin on the board from (1,1)->(2,2). This coin cannot be moved any further. And so, the Chef wins.
Notice that if the Chef moves it to any other valid position, i.e. either to (1,2) or (2,1) he will lose!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
ICPC World Finals Day 6

Russian Constructivism is an art movement in the Soviet Union that began in the mid-1910s. Inspired by such things, Tee, who had been in Country R for a long time, decided to create a cool design despite the rehearsal of the ICPC World Finals. Mr. Tee says: "A circle and a line segment are enough for the symbol. It is important how beautifully the line segments intersect."

problem

Assign \\ (n \\) coordinates \\ (1, 2,…, n \\) to the circumference at equal intervals. There is exactly one line segment from each coordinate, and the line segment of the coordinate \\ (i \\) is connected to a different coordinate \\ (a_ {i} \\). (Conversely, the line segment of the coordinate \\ (a_ {i} \\) is connected to the coordinate \\ (a_ {a_ {i}} = i \\).) From this state, at most \\ (k) \\) You can reconnect the line segments of a book (freely regardless of coordinates and length) on the circumference. Answer the maximum size of a set of line segments that intersect each other.

input


n k
a1 a2… an


The number of coordinates \\ (n \\) and the number of line segments that can be reconnected \\ (k \\) are given on the first line, separated by blanks. On the second line, \\ (a_ {i} \\) representing the coordinates connecting the line segments of the coordinates \\ (i \\) is given, separated by blanks.

output

At most \\ (k \\) After reconnecting the line segments, output the maximum size of the set of line segments that intersect each other on one line.

Constraint

* \\ (2 \ leq n \ leq 8000 \\)
* \\ (n \\) is an even number
* \\ (0 \ leq k \ leq \ min (n / 2, 20) \\)
* \\ (1 \ leq a_ {i} \ leq n \\)
* \\ (a_ {i} \ not = i \\)
* Never connect a line segment to yourself
* \\ (a_ {i} \ not = a_ {j} (i \ not = j) \\)
* No more than one line segment can be connected at the same coordinates
* \\ (a_ {a_ {i}} = i \\)
* If a line segment is connected from \\ (i \\) to \\ (j \\), a line segment is connected from \\ (j \\) to \\ (i \\)



Input / output example

Input 1


8 0
7 4 6 2 8 3 1 5


Output 1


2


The line segments that intersect each other are represented by the red line segments in the figure below.

http://k-operafan.info/static/uecpc2013/files/art_sample_1.png

Input 2


8 1
7 4 6 2 8 3 1 5


Output 2


3


By reconnecting the line segments connecting 1 and 7 as shown in the figure below, three line segments that intersect each other can be obtained.

http://k-operafan.info/static/uecpc2013/files/art_sample_2.png

Input 3


8 0
5 6 7 8 1 2 3 4


Output 3


Four


Since all line segments intersect each other, the maximum number of intersecting line segments is four.

http://k-operafan.info/static/uecpc2013/files/art_sample_3.png





Example

Input

n k
a


Output

2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string s, consisting of lowercase English letters, and the integer m.

One should choose some symbols from the given string so that any contiguous subsegment of length m has at least one selected symbol. Note that here we choose positions of symbols, not the symbols themselves.

Then one uses the chosen symbols to form a new string. All symbols from the chosen position should be used, but we are allowed to rearrange them in any order.

Formally, we choose a subsequence of indices 1 ≤ i_1 < i_2 < ... < i_{t} ≤ |s|. The selected sequence must meet the following condition: for every j such that 1 ≤ j ≤ |s| - m + 1, there must be at least one selected index that belongs to the segment [j,  j + m - 1], i.e. there should exist a k from 1 to t, such that j ≤ i_{k} ≤ j + m - 1.

Then we take any permutation p of the selected indices and form a new string s_{i}_{p}_1s_{i}_{p}_2... s_{i}_{p}_{t}.

Find the lexicographically smallest string, that can be obtained using this procedure.


-----Input-----

The first line of the input contains a single integer m (1 ≤ m ≤ 100 000).

The second line contains the string s consisting of lowercase English letters. It is guaranteed that this string is non-empty and its length doesn't exceed 100 000. It is also guaranteed that the number m doesn't exceed the length of the string s.


-----Output-----

Print the single line containing the lexicographically smallest string, that can be obtained using the procedure described above.


-----Examples-----
Input
3
cbabc

Output
a

Input
2
abcab

Output
aab

Input
3
bcabcbaccba

Output
aaabb



-----Note-----

In the first sample, one can choose the subsequence {3} and form a string "a".

In the second sample, one can choose the subsequence {1, 2, 4} (symbols on this positions are 'a', 'b' and 'a') and rearrange the chosen symbols to form a string "aab".

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