vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You have a string $s$ of length $n$ consisting of only characters > and <. You may do some operations with this string, for each operation you have to choose some character that still remains in the string. If you choose a character >, the character that comes right after it is deleted (if the character you chose was the last one, nothing happens). If you choose a character <, the character that comes right before it is deleted (if the character you chose was the first one, nothing happens).

For example, if we choose character > in string > > < >, the string will become to > > >. And if we choose character < in string > <, the string will become to <.

The string is good if there is a sequence of operations such that after performing it only one character will remain in the string. For example, the strings >, > > are good. 

Before applying the operations, you may remove any number of characters from the given string (possibly none, possibly up to $n - 1$, but not the whole string). You need to calculate the minimum number of characters to be deleted from string $s$ so that it becomes good.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 100$) – the number of test cases. Each test case is represented by two lines.

The first line of $i$-th test case contains one integer $n$ ($1 \le n \le 100$) – the length of string $s$.

The second line of $i$-th test case contains string $s$, consisting of only characters > and <.


-----Output-----

For each test case print one line.

For $i$-th test case print the minimum number of characters to be deleted from string $s$ so that it becomes good.


-----Example-----
Input
3
2
<>
3
><<
1
>

Output
1
0
0



-----Note-----

In the first test case we can delete any character in string <>.

In the second test case we don't need to delete any characters. The string > < < is good, because we can perform the following sequence of operations: > < < $\rightarrow$ < < $\rightarrow$ <.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Shaka and his brother have created a boring game which is played like this:  

They take a word composed of lowercase English letters and try to get the maximum possible score by building exactly 2 palindromic subsequences. The score obtained is the product of the length of these 2 subsequences.

Let's say $\mbox{A}$ and $\mbox{B}$ are two subsequences from the initial string. If $A_i$ & $A_j$ are the smallest and the largest positions (from the initial word) respectively in $\mbox{A}$ ; and $B_i$ & $B_j$ are the smallest and the largest positions (from the initial word) respectively in $\mbox{B}$, then the following statements hold true: 

$A_i\leq A_j$, 

$B_i\leq B_j$, & 

$A_j<B_i$. 

i.e., the positions of the subsequences should not cross over each other. 

Hence the score obtained is the product of lengths of subsequences $\mbox{A}$ & $\mbox{B}$. Such subsequences can be numerous for a larger initial word, and hence it becomes harder to find out the maximum possible score. Can you help Shaka and his brother find this out?

Input Format

Input contains a word $\mbox{S}$ composed of lowercase English letters in a single line.  

Constraints

$1<|S|\leq3000$ 

each character will be a lower case english alphabet.  

Output Format

Output the maximum score the boys can get from $\mbox{S}$.

Sample Input
eeegeeksforskeeggeeks

Sample Output
50

Explanation

A possible optimal solution is eee-g-ee-ksfor-skeeggeeks being eeeee the one subsequence and skeeggeeks the other one. We can also select eegee in place of eeeee, as both have the same length.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider placing N flags on a line. Flags are numbered through 1 to N.

Flag i can be placed on the coordinate X_i or Y_i. For any two different flags, the distance between them should be at least D.

Decide whether it is possible to place all N flags. If it is possible, print such a configulation.

Constraints

* 1 \leq N \leq 1000
* 0 \leq D \leq 10^9
* 0 \leq X_i < Y_i \leq 10^9
* All values in Input are integer.

Input

Input is given from Standard Input in the following format:


N D
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N


Output

Print `No` if it is impossible to place N flags.

If it is possible, print `Yes` first. After that, print N lines. i-th line of them should contain the coodinate of flag i.

Examples

Input

3 2
1 4
2 5
0 6


Output

Yes
4
2
0


Input

3 3
1 4
2 5
0 6


Output

No

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a grid of squares with H+1 horizontal rows and W vertical columns.

You will start at one of the squares in the top row and repeat moving one square right or down. However, for each integer i from 1 through H, you cannot move down from the A_i-th, (A_i + 1)-th, \ldots, B_i-th squares from the left in the i-th row from the top.

For each integer k from 1 through H, find the minimum number of moves needed to reach one of the squares in the (k+1)-th row from the top. (The starting square can be chosen individually for each case.) If, starting from any square in the top row, none of the squares in the (k+1)-th row can be reached, print `-1` instead.

Constraints

* 1 \leq H,W \leq 2\times 10^5
* 1 \leq A_i \leq B_i \leq W

Input

Input is given from Standard Input in the following format:


H W
A_1 B_1
A_2 B_2
:
A_H B_H


Output

Print H lines. The i-th line should contain the answer for the case k=i.

Example

Input

4 4
2 4
1 1
2 3
2 4


Output

1
3
6
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Wilbur the pig is tinkering with arrays again. He has the array a_1, a_2, ..., a_{n} initially consisting of n zeros. At one step, he can choose any index i and either add 1 to all elements a_{i}, a_{i} + 1, ... , a_{n} or subtract 1 from all elements a_{i}, a_{i} + 1, ..., a_{n}. His goal is to end up with the array b_1, b_2, ..., b_{n}. 

Of course, Wilbur wants to achieve this goal in the minimum number of steps and asks you to compute this value.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the length of the array a_{i}. Initially a_{i} = 0 for every position i, so this array is not given in the input.

The second line of the input contains n integers b_1, b_2, ..., b_{n} ( - 10^9 ≤ b_{i} ≤ 10^9).


-----Output-----

Print the minimum number of steps that Wilbur needs to make in order to achieve a_{i} = b_{i} for all i.


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

Output
5
Input
4
1 2 2 1

Output
3


-----Note-----

In the first sample, Wilbur may successively choose indices 1, 2, 3, 4, and 5, and add 1 to corresponding suffixes.

In the second sample, Wilbur first chooses indices 1 and 2 and adds 1 to corresponding suffixes, then he chooses index 4 and subtract 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The rgb function is incomplete. Complete it so that passing in RGB decimal values will result in a hexadecimal representation being returned. Valid decimal values for RGB are 0 - 255. Any values that fall out of that range must be rounded to the closest valid value.

Note: Your answer should always be 6 characters long, the shorthand with 3 will not work here.

The following are examples of  expected output values:
```python
rgb(255, 255, 255) # returns FFFFFF
rgb(255, 255, 300) # returns FFFFFF
rgb(0,0,0) # returns 000000
rgb(148, 0, 211) # returns 9400D3
```
```if:nasm

char \*rgb(int r, int g, int b, char \*outp)

```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
If I give you a date, can you tell me what day that date is? For example, december 8th, 2015 is a tuesday.

Your job is to write the function ```day(d)```
which takes a string representation of a date as input, in the format YYYYMMDD. The example would be "20151208". The function needs to output the string representation of the day, so in this case ```"Tuesday"```.

Your function should be able to handle dates ranging from January first, 1582 (the year the Gregorian Calendar was introduced) to December 31st, 9999. You will not be given invalid dates. Remember to take leap years into account.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One must train much to do well on wizardry contests. So, there are numerous wizardry schools and magic fees.

One of such magic schools consists of *n* tours. A winner of each tour gets a huge prize. The school is organised quite far away, so one will have to take all the prizes home in one go. And the bags that you've brought with you have space for no more than *k* huge prizes.

Besides the fact that you want to take all the prizes home, you also want to perform well. You will consider your performance good if you win at least *l* tours.

In fact, years of organizing contests proved to the organizers that transporting huge prizes is an issue for the participants. Alas, no one has ever invented a spell that would shrink the prizes... So, here's the solution: for some tours the winner gets a bag instead of a huge prize. Each bag is characterized by number *a**i* — the number of huge prizes that will fit into it.

You already know the subject of all tours, so you can estimate the probability *p**i* of winning the *i*-th tour. You cannot skip the tour under any circumstances.

Find the probability that you will perform well on the contest and will be able to take all won prizes home (that is, that you will be able to fit all the huge prizes that you won into the bags that you either won or brought from home).

Input Specification:
The first line contains three integers *n*, *l*, *k* (1<=≤<=*n*<=≤<=200,<=0<=≤<=*l*,<=*k*<=≤<=200) — the number of tours, the minimum number of tours to win, and the number of prizes that you can fit in the bags brought from home, correspondingly.

The second line contains *n* space-separated integers, *p**i* (0<=≤<=*p**i*<=≤<=100) — the probability to win the *i*-th tour, in percents.

The third line contains *n* space-separated integers, *a**i* (1<=≤<=*a**i*<=≤<=200) — the capacity of the bag that will be awarded to you for winning the *i*-th tour, or else -1, if the prize for the *i*-th tour is a huge prize and not a bag.

Output Specification:
Print a single real number — the answer to the problem. The answer will be accepted if the absolute or relative error does not exceed 10<=-<=6.

Demo Input:
['3 1 0\n10 20 30\n-1 -1 2\n', '1 1 1\n100\n123\n']

Demo Output:
['0.300000000000\n', '1.000000000000\n']

Note:
In the first sample we need either win no tour or win the third one. If we win nothing we wouldn't perform well. So, we must to win the third tour. Other conditions will be satisfied in this case. Probability of wining the third tour is 0.3.

In the second sample we win the only tour with probability 1.0, and go back home with bag for it.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nauuo is a girl who loves traveling.

One day she went to a tree, Old Driver Tree, literally, a tree with an old driver on it.

The tree is a connected graph consisting of n nodes and n-1 edges. Each node has a color, and Nauuo will visit the ODT through a simple path on the tree in the old driver's car.

Nauuo wants to visit see more different colors in her journey, but she doesn't know which simple path she will be traveling on. So, she wants to calculate the sum of the numbers of different colors on all different paths. Can you help her?

What's more, the ODT is being redecorated, so there will be m modifications, each modification will change a single node's color. Nauuo wants to know the answer after each modification too.

Note that in this problem, we consider the simple path from u to v and the simple path from v to u as two different simple paths if and only if u≠ v.

Input

The first line contains two integers n and m (2≤ n≤ 4⋅ 10^5, 1≤ m≤ 4⋅ 10^5) — the number of nodes and the number of modifications.

The second line contains n integers c_1,c_2,…,c_n (1≤ c_i≤ n), where c_i is the initial color of node i.

Each of the next n-1 lines contains two integers u and v (1≤ u,v≤ n), denoting there is an edge between u and v. It is guaranteed that the given edges form a tree.

Each of the next m lines contains two integers u and x (1≤ u,x≤ n), which means a modification that changes the color of node u into x.

Output

The output contains m+1 integers — the first integer is the answer at the beginning, the rest integers are the answers after every modification in the given order.

Examples

Input


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


Output


47
51
49
45


Input


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


Output


36
46

Note

Example 1

<image>

The number of colors on each simple path at the beginning:

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A sequence of square brackets is regular if by inserting symbols "+" and "1" into it, you can get a regular mathematical expression from it. For example, sequences "[[]][]", "[]" and "[[][[]]]" — are regular, at the same time "][", "[[]" and "[[]]][" — are irregular. 

Draw the given sequence using a minimalistic pseudographics in the strip of the lowest possible height — use symbols '+', '-' and '|'. For example, the sequence "[[][]][]" should be represented as: 

+-        -++- -+    

|+- -++- -+||   |

||   ||   |||   |

|+- -++- -+||   |

+-        -++- -+



Each bracket should be represented with the hepl of one or more symbols '|' (the vertical part) and symbols '+' and '-' as on the example which is given above.

Brackets should be drawn without spaces one by one, only dividing pairs of consecutive pairwise brackets with a single-space bar (so that the two brackets do not visually merge into one symbol). The image should have the minimum possible height. 

The enclosed bracket is always smaller than the surrounding bracket, but each bracket separately strives to maximize the height of the image. So the pair of final brackets in the example above occupies the entire height of the image.

Study carefully the examples below, they adequately explain the condition of the problem. Pay attention that in this problem the answer (the image) is unique. 


-----Input-----

The first line contains an even integer n (2 ≤ n ≤ 100) — the length of the sequence of brackets.

The second line contains the sequence of brackets — these are n symbols "[" and "]". It is guaranteed that the given sequence of brackets is regular. 


-----Output-----

Print the drawn bracket sequence in the format which is given in the condition. Don't print extra (unnecessary) spaces. 


-----Examples-----
Input
8
[[][]][]

Output
+-        -++- -+
|+- -++- -+||   |
||   ||   |||   |
|+- -++- -+||   |
+-        -++- -+

Input
6
[[[]]]

Output
+-     -+
|+-   -+|
||+- -+||
|||   |||
||+- -+||
|+-   -+|
+-     -+

Input
6
[[][]]

Output
+-        -+
|+- -++- -+|
||   ||   ||
|+- -++- -+|
+-        -+

Input
2
[]

Output
+- -+
|   |
+- -+

Input
4
[][]

Output
+- -++- -+
|   ||   |
+- -++- -+

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

Time Limit: 1 seconds

Memory Limit: 256 megabytes

Problem Description:
Theatre Square in the capital city of Berland has a rectangular shape with the size *n*<=×<=*m* meters. On the occasion of the city's anniversary, a decision was taken to pave the Square with square granite flagstones. Each flagstone is of the size *a*<=×<=*a*.

What is the least number of flagstones needed to pave the Square? It's allowed to cover the surface larger than the Theatre Square, but the Square has to be covered. It's not allowed to break the flagstones. The sides of flagstones should be parallel to the sides of the Square.

Input Specification:
The input contains three positive integer numbers in the first line: *n*,<=<=*m* and *a* (1<=≤<=<=*n*,<=*m*,<=*a*<=≤<=109).

Output Specification:
Write the needed number of flagstones.

Demo Input:
['6 6 4\n']

Demo Output:
['4\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke has X+Y balls. X of them have an integer A written on them, and the other Y of them have an integer B written on them.

Snuke will divide these balls into some number of groups. Here, every ball should be contained in exactly one group, and every group should contain one or more balls.

A group is said to be good when the sum of the integers written on the balls in that group is a multiple of an integer C. Find the maximum possible number of good groups.

Solve T test cases for each input file.

Constraints

* 1 \leq T \leq 2 \times 10^4
* 1 \leq A,X,B,Y,C \leq 10^9
* A \neq B

Input

Input is given from Standard Input in the following format. The first line is as follows:


T


Then, T test cases follow. Each test case is given in the following format:


A X B Y C


Output

For each test case, print a line containing the maximum possible number of good groups.

Example

Input

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


Output

2
2
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a set S of N points in a two-dimensional plane. The coordinates of the i-th point are (x_i, y_i). The N points have distinct x-coordinates and distinct y-coordinates.
For a non-empty subset T of S, let f(T) be the number of points contained in the smallest rectangle, whose sides are parallel to the coordinate axes, that contains all the points in T. More formally, we define f(T) as follows:
 - f(T) :=  (the number of integers i (1 \leq i \leq N) such that a \leq x_i \leq b and c \leq y_i \leq d, where a, b, c, and d are the minimum x-coordinate, the maximum x-coordinate, the minimum y-coordinate, and the maximum y-coordinate of the points in T)
Find the sum of f(T) over all non-empty subset T of S. Since it can be enormous, print the sum modulo 998244353.

-----Constraints-----
 - 1 \leq N \leq 2 \times 10^5
 - -10^9 \leq x_i, y_i \leq 10^9
 - x_i \neq x_j (i \neq j)
 - y_i \neq y_j (i \neq j)
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
x_1 y_1
:
x_N y_N

-----Output-----
Print the sum of f(T) over all non-empty subset T of S, modulo 998244353.

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

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

Let the first, second, and third points be P_1, P_2, and P_3, respectively. S = \{P_1, P_2, P_3\} has seven non-empty subsets, and f has the following values for each of them:
 - f(\{P_1\}) = 1
 - f(\{P_2\}) = 1
 - f(\{P_3\}) = 1
 - f(\{P_1, P_2\}) = 2
 - f(\{P_2, P_3\}) = 2
 - f(\{P_3, P_1\}) = 3
 - f(\{P_1, P_2, P_3\}) = 3
The sum of these is 13.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string A and a dictionary of n words B, find out if A can be segmented into a space-separated sequence of dictionary words. 
Example 1:
Input:
n = 12
B = { "i", "like", "sam", "sung", "samsung",
"mobile","ice","cream", "icecream", "man",
"go", "mango" }, A = "ilike"
Output: 1
Explanation: The string can be segmented as
"i like".
Example 2:
Input: 
n = 12 
B = { "i", "like", "sam", "sung", "samsung",
"mobile","ice","cream", "icecream", "man", 
"go", "mango" }, A = "ilikesamsung" 
Output: 1
Explanation: The string can be segmented as 
"i like samsung" or "i like sam sung".
Your Task:
Complete wordBreak() function which takes a string and list of strings as a parameter and returns 1 if it is possible to break words, else return 0. You don't need to read any input or print any output, it is done by driver code.
Expected time complexity: O(n*l+|A|^{2}) where l is the leght of longest string present in the dictionary and |A| is the length of string A
Expected auxiliary space: O(|A| + k) , where k = sum of length of all strings present in B
 
Constraints:
1 <= N <= 12
1 <= s <=1000 , where s = length of string A
 The length of each word is less than 15.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Feynman's squares
Richard Phillips Feynman was a well-known American physicist and a recipient of the Nobel Prize in Physics. He worked in theoretical physics and pioneered the field of quantum computing.

Recently, an old farmer found some papers and notes that are believed to have belonged to Feynman. Among notes about mesons and electromagnetism, there was a napkin where he wrote a simple puzzle: "how many different squares are there in a grid of NxN squares?".

For example, when N=2, the answer is 5: the 2x2 square itself, plus the four 1x1 squares in its corners:



# Task

You have to write a function

```python
def count_squares(n):
```

that solves Feynman's question in general. The input to your function will always be a positive integer.

#Examples

```python
count_squares(1) =  1
count_squares(2) =  5
count_squares(3) = 14
```

(Adapted from the Sphere Online Judge problem SAMER08F by Diego Satoba)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Princess Twilight went to Celestia and Luna's old castle to research the chest from the Elements of Harmony.

<image>

A sequence of positive integers bi is harmony if and only if for every two elements of the sequence their greatest common divisor equals 1. According to an ancient book, the key of the chest is a harmony sequence bi which minimizes the following expression:

<image>

You are given sequence ai, help Princess Twilight to find the key.

Input

The first line contains an integer n (1 ≤ n ≤ 100) — the number of elements of the sequences a and b. The next line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 30).

Output

Output the key — sequence bi that minimizes the sum described above. If there are multiple optimal sequences, you can output any of them.

Examples

Input

5
1 1 1 1 1


Output

1 1 1 1 1 

Input

5
1 6 4 2 8


Output

1 5 3 1 8 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This kata is a continuation of [Part 1](http://www.codewars.com/kata/the-fibfusc-function-part-1). The `fibfusc` function is defined recursively as follows:

    fibfusc(0) = (1, 0)
    fibfusc(1) = (0, 1)
    fibfusc(2n) = ((x + y)(x - y), y(2x + 3y)), where (x, y) = fibfusc(n)
    fibfusc(2n + 1) = (-y(2x + 3y), (x + 2y)(x + 4y)), where (x, y) = fibfusc(n)

Your job is to produce the code for the `fibfusc` function. In this kata, your function will be tested with large values of n (up to 2000 bits), so you should be concerned about stack overflow and timeouts. Moreover, since the `fibfusc` function grows exponentially, your function should take an extra argument `num_digits` with a default value of `None`. When not `None`, `num_digits` takes a positive `int` value and the returned values shall be truncated to the last `num_digits` digits. 

For example, let `n = 101`. With `num_digits` not set or set to `None`, `fibfusc` should return: 
`(-280571172992510140037611932413038677189525L, 734544867157818093234908902110449296423351L)`. If `num_digits = 12`, the function should return `(-38677189525L, 449296423351L)`. Notice in particular, that for any value of `n` greater than 1, `x` is negative, and the truncated value of `x` should also be negative.

Hint 1: Use modulo `10 ** num_digits` arithmetic to keep all intermediary results small.

Hint 2: Consider using an iterative ["number climber"](http://www.codewars.com/kata/number-climber) to avoid stack overflows.

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