vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Sereja and Intervals

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Sereja is interested in intervals of numbers, so he has prepared a problem about intervals for you. An interval of numbers is a pair of integers [*l*,<=*r*] (1<=≤<=*l*<=≤<=*r*<=≤<=*m*). Interval [*l*1,<=*r*1] belongs to interval [*l*2,<=*r*2] if the following condition is met: *l*2<=≤<=*l*1<=≤<=*r*1<=≤<=*r*2.

Sereja wants to write out a sequence of *n* intervals [*l*1,<=*r*1], [*l*2,<=*r*2], ..., [*l**n*,<=*r**n*] on a piece of paper. At that, no interval in the sequence can belong to some other interval of the sequence. Also, Sereja loves number *x* very much and he wants some (at least one) interval in the sequence to have *l**i*<==<=*x*. Sereja wonders, how many distinct ways to write such intervals are there?

Help Sereja and find the required number of ways modulo 1000000007 (109<=+<=7).

Two ways are considered distinct if there is such *j* (1<=≤<=*j*<=≤<=*n*), that the *j*-th intervals in two corresponding sequences are not equal.

Input Specification:
The first line contains integers *n*, *m*, *x* (1<=≤<=*n*·*m*<=≤<=100000,<=1<=≤<=*x*<=≤<=*m*) — the number of segments in the sequence, the constraints on the numbers in segments and Sereja's favourite number.

Output Specification:
In a single line print the answer modulo 1000000007 (109<=+<=7).

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

Demo Output:
['1\n', '240\n', '6\n']

Note:
In third example next sequences will be correct: {[1, 1], [3, 3]}, {[1, 2], [3, 3]}, {[2, 2], [3, 3]}, {[3, 3], [1, 1]}, {[3, 3], [2, 2]}, {[3, 3], [1, 2]}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A set of frogs have accidentally fallen to the bottom of a large pit. Their only means of escaping the pit is to jump out of it. Each frog $i$ is described by three parameters $(l_ i,w_ i,h_ i)$ where $l_ i$ is its leap capacity, $w_ i$ its weight, and $h_ i$ its height. The leap capacity specifies how high that frog can jump. If a frog’s leap capacity is strictly larger than the depth of the pit, the frog can directly escape the pit. However, these frogs are altruistic. Rather than selfishly saving themselves and leaving the frogs with too limited leap capacity behind, they collectively aim to save as many of them from the pit as possible. 

The frogs realize that if a frog $A$ climbs up on the back of frog $B$ before it jumps, the first frog $A$ stands a better chance of escaping the pit: it can escape if $h_ B+l_ A$ is strictly larger than the depth of the pit.

Furthermore, if frog $B$ carrying frog $A$ on its back climbs up on the back of frog $C$, the situation is even better for frog $A$: it can now escape the pit if $h_ C+h_ B+l_ A$ is strictly larger than the depth of the pit.

The frogs can build even higher piles of frogs this way, the only restriction is that no frog may carry other frogs of weight in total amounting to its own weight or heavier. Once a pile has been used to allow a frog to escape, the frogs in the pile jump back to the bottom of the pit and they can then form a new pile (possibly consisting of a different set of frogs). The question is simply how many frogs can escape the pit assuming they collaborate to maximize this number?

-----Input-----
The first line of input contains two integers $n$ and $d$ ($1 \le n \leq 100000$, $1 \le d \le 10^8$), where $n$ is the number of frogs and $d$ is the depth of the pit in µm. Then follow $n$ lines each containing three integers $l, w, h$ ($1 \le l, w, h \le 10^8$), representing a frog with leap capacity $l$ µm, weight $w$ µg, and height $h$ µm. The sum of all frogs’ weights is at most $10^8$ µg.

-----Output-----
Output the maximum number of frogs that can escape the pit.

-----Examples-----
Sample Input:
3 19
15 5 3
12 4 4
20 10 5
Sample Output:
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n balls. They are arranged in a row. Each ball has a color (for convenience an integer) and an integer value. The color of the i-th ball is ci and the value of the i-th ball is vi.

Squirrel Liss chooses some balls and makes a new sequence without changing the relative order of the balls. She wants to maximize the value of this sequence.

The value of the sequence is defined as the sum of following values for each ball (where a and b are given constants):

  * If the ball is not in the beginning of the sequence and the color of the ball is same as previous ball's color, add (the value of the ball)  ×  a. 
  * Otherwise, add (the value of the ball)  ×  b. 



You are given q queries. Each query contains two integers ai and bi. For each query find the maximal value of the sequence she can make when a = ai and b = bi.

Note that the new sequence can be empty, and the value of an empty sequence is defined as zero.

Input

The first line contains two integers n and q (1 ≤ n ≤ 105; 1 ≤ q ≤ 500). The second line contains n integers: v1, v2, ..., vn (|vi| ≤ 105). The third line contains n integers: c1, c2, ..., cn (1 ≤ ci ≤ n).

The following q lines contain the values of the constants a and b for queries. The i-th of these lines contains two integers ai and bi (|ai|, |bi| ≤ 105).

In each line integers are separated by single spaces.

Output

For each query, output a line containing an integer — the answer to the query. The i-th line contains the answer to the i-th query in the input order.

Please, do not write 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

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


Output

20
9
4


Input

4 1
-3 6 -1 2
1 2 3 1
1 -1


Output

5

Note

In the first example, to achieve the maximal value:

  * In the first query, you should select 1st, 3rd, and 4th ball. 
  * In the second query, you should select 3rd, 4th, 5th and 6th ball. 
  * In the third query, you should select 2nd and 4th ball. 



Note that there may be other ways to achieve the maximal value.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This year Alex has finished school, and now he is a first-year student of Berland State University. For him it was a total surprise that even though he studies programming, he still has to attend physical education lessons. The end of the term is very soon, but, unfortunately, Alex still hasn't attended a single lesson!

Since Alex doesn't want to get expelled, he wants to know the number of working days left until the end of the term, so he can attend physical education lessons during these days. But in BSU calculating the number of working days is a complicated matter:

There are n days left before the end of the term (numbered from 1 to n), and initially all of them are working days. Then the university staff sequentially publishes q orders, one after another. Each order is characterised by three numbers l, r and k:

  * If k = 1, then all days from l to r (inclusive) become non-working days. If some of these days are made working days by some previous order, then these days still become non-working days; 
  * If k = 2, then all days from l to r (inclusive) become working days. If some of these days are made non-working days by some previous order, then these days still become working days. 



Help Alex to determine the number of working days left after each order!

Input

The first line contains one integer n, and the second line — one integer q (1 ≤ n ≤ 109, 1 ≤ q ≤ 3·105) — the number of days left before the end of the term, and the number of orders, respectively.

Then q lines follow, i-th line containing three integers li, ri and ki representing i-th order (1 ≤ li ≤ ri ≤ n, 1 ≤ ki ≤ 2).

Output

Print q integers. i-th of them must be equal to the number of working days left until the end of the term after the first i orders are published.

Example

Input

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


Output

2
0
2
3
1
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
On the eve of New Year in Dholakpur, Chota Bheem and Chutki are playing a game, described as follows. 

There are two plates full of Laddus. Both can eat 'L' (L ≥ 1) laddus from any one plate or 'L' laddus from both the plates in each step. They play the game alternatively and the last one to eat the laddu will be the winner.

As Chota Bheem wants to impress Chutki, he wants to make Chutki the winner. You have to help Chota Bheem in deciding who should play first.

Input:

The first line of input contains an integer T denoting the number of test cases.

Each line of test case contains 2 numbers 'a' and 'b', the number of laddus in each plate respectively.

Output:

For each test case, output a single word "Bheem" or "Chutki" denoting the player who should play first.

Constraints:

1 ≤ T ≤ 100000

0 ≤ a,b ≤ 1000000

SAMPLE INPUT
3
1 2
1 3
2 0

SAMPLE OUTPUT
Bheem
Chutki
Chutki

Explanation

In test case 1, from (1,2) we can reach (1,1) or (0,1) or (0,2) which are all winnning cases so Bheem plays first.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice and Bob decided to eat some fruit. In the kitchen they found a large bag of oranges and apples. Alice immediately took an orange for herself, Bob took an apple. To make the process of sharing the remaining fruit more fun, the friends decided to play a game. They put multiple cards and on each one they wrote a letter, either 'A', or the letter 'B'. Then they began to remove the cards one by one from left to right, every time they removed a card with the letter 'A', Alice gave Bob all the fruits she had at that moment and took out of the bag as many apples and as many oranges as she had before. Thus the number of oranges and apples Alice had, did not change. If the card had written letter 'B', then Bob did the same, that is, he gave Alice all the fruit that he had, and took from the bag the same set of fruit. After the last card way removed, all the fruit in the bag were over.

You know how many oranges and apples was in the bag at first. Your task is to find any sequence of cards that Alice and Bob could have played with.


-----Input-----

The first line of the input contains two integers, x, y (1 ≤ x, y ≤ 10^18, xy > 1) — the number of oranges and apples that were initially in the bag.


-----Output-----

Print any sequence of cards that would meet the problem conditions as a compressed string of characters 'A' and 'B. That means that you need to replace the segments of identical consecutive characters by the number of repetitions of the characters and the actual character. For example, string AAABAABBB should be replaced by string 3A1B2A3B, but cannot be replaced by 2A1A1B2A3B or by 3AB2A3B. See the samples for clarifications of the output format. The string that you print should consist of at most 10^6 characters. It is guaranteed that if the answer exists, its compressed representation exists, consisting of at most 10^6 characters. If there are several possible answers, you are allowed to print any of them.

If the sequence of cards that meet the problem statement does not not exist, print a single word Impossible.


-----Examples-----
Input
1 4

Output
3B

Input
2 2

Output
Impossible

Input
3 2

Output
1A1B



-----Note-----

In the first sample, if the row contained three cards with letter 'B', then Bob should give one apple to Alice three times. So, in the end of the game Alice has one orange and three apples, and Bob has one apple, in total it is one orange and four apples.

In second sample, there is no answer since one card is not enough for game to finish, and two cards will produce at least three apples or three oranges.

In the third sample, cards contain letters 'AB', so after removing the first card Bob has one orange and one apple, and after removal of second card Alice has two oranges and one apple. So, in total it is three oranges and two apples.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Once upon a time, there was a king who loved beautiful costumes very much. The king had a special cocoon bed to make excellent cloth of silk. The cocoon bed had 16 small square rooms, forming a 4 × 4 lattice, for 16 silkworms. The cocoon bed can be depicted as follows:

<image>

The cocoon bed can be divided into 10 rectangular boards, each of which has 5 slits:

<image>

Note that, except for the slit depth, there is no difference between the left side and the right side of the board (or, between the front and the back); thus, we cannot distinguish a symmetric board from its rotated image as is shown in the following:

<image>

Slits have two kinds of depth, either shallow or deep. The cocoon bed should be constructed by fitting five of the boards vertically and the others horizontally, matching a shallow slit with a deep slit.

Your job is to write a program that calculates the number of possible configurations to make the lattice. You may assume that there is no pair of identical boards. Notice that we are interested in the number of essentially different configurations and therefore you should not count mirror image configurations and rotated configurations separately as different configurations.

The following is an example of mirror image and rotated configurations, showing vertical and horizontal boards separately, where shallow and deep slits are denoted by '1' and '0' respectively.

<image>

Notice that a rotation may exchange position of a vertical board and a horizontal board.



Input

The input consists of multiple data sets, each in a line. A data set gives the patterns of slits of 10 boards used to construct the lattice. The format of a data set is as follows:


XXXXX XXXXX XXXXX XXXXX XXXXX XXXXX XXXXX XXXXX XXXXX XXXXX


Each x is either '0' or '1'. '0' means a deep slit, and '1' a shallow slit. A block of five slit descriptions corresponds to a board. There are 10 blocks of slit descriptions in a line. Two adjacent blocks are separated by a space.

For example, the first data set in the Sample Input means the set of the following 10 boards:

<image>

The end of the input is indicated by a line consisting solely of three characters "END".

Output

For each data set, the number of possible configurations to make the lattice from the given 10 boards should be output, each in a separate line.

Example

Input

10000 01000 00100 11000 01100 11111 01110 11100 10110 11110
10101 01000 00000 11001 01100 11101 01110 11100 10110 11010
END


Output

40
6

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The employees of the R1 company often spend time together: they watch football, they go camping, they solve contests. So, it's no big deal that sometimes someone pays for someone else.

Today is the day of giving out money rewards. The R1 company CEO will invite employees into his office one by one, rewarding each one for the hard work this month. The CEO knows who owes money to whom. And he also understands that if he invites person *x* to his office for a reward, and then immediately invite person *y*, who has lent some money to person *x*, then they can meet. Of course, in such a situation, the joy of person *x* from his brand new money reward will be much less. Therefore, the R1 CEO decided to invite the staff in such an order that the described situation will not happen for any pair of employees invited one after another.

However, there are a lot of employees in the company, and the CEO doesn't have a lot of time. Therefore, the task has been assigned to you. Given the debt relationships between all the employees, determine in which order they should be invited to the office of the R1 company CEO, or determine that the described order does not exist.

Input Specification:
The first line contains space-separated integers *n* and *m*  — the number of employees in R1 and the number of debt relations. Each of the following *m* lines contains two space-separated integers *a**i*, *b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*; *a**i*<=≠<=*b**i*), these integers indicate that the person number *a**i* owes money to a person a number *b**i*. Assume that all the employees are numbered from 1 to *n*.

It is guaranteed that each pair of people *p*, *q* is mentioned in the input data at most once. In particular, the input data will not contain pairs *p*, *q* and *q*, *p* simultaneously.

Output Specification:
Print -1 if the described order does not exist. Otherwise, print the permutation of *n* distinct integers. The first number should denote the number of the person who goes to the CEO office first, the second number denote the person who goes second and so on.

If there are multiple correct orders, you are allowed to print any of them.

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

Demo Output:
['2 1 \n', '2 1 3 \n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array of n integers a_1, a_2, …, a_n.

You will perform q operations. In the i-th operation, you have a symbol s_i which is either "<" or ">" and a number x_i.

You make a new array b such that b_j = -a_j if a_j s_i x_i and b_j = a_j otherwise (i.e. if s_i is '>', then all a_j > x_i will be flipped). After doing all these replacements, a is set to be b.

You want to know what your final array looks like after all operations.

Input

The first line contains two integers n,q (1 ≤ n,q ≤ 10^5) — the number of integers and the number of queries.

The next line contains n integers a_1, a_2, …, a_n (-10^5 ≤ a_i ≤ 10^5) — the numbers.

Each of the next q lines contains a character and an integer s_i, x_i. (s_i ∈ \{<, >\}, -10^5 ≤ x_i ≤ 10^5) – the queries.

Output

Print n integers c_1, c_2, …, c_n representing the array after all operations.

Examples

Input


11 3
-5 -4 -3 -2 -1 0 1 2 3 4 5
&gt; 2
&gt; -4
&lt; 5


Output


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


Input


5 5
0 1 -2 -1 2
&lt; -2
&lt; -1
&lt; 0
&lt; 1
&lt; 2


Output


0 -1 2 -1 2

Note

In the first example, the array goes through the following changes: 

  * Initial: [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5] 
  * > 2: [-5, -4, -3, -2, -1, 0, 1, 2, -3, -4, -5] 
  * > -4: [-5, -4, 3, 2, 1, 0, -1, -2, 3, -4, -5] 
  * < 5: [5, 4, -3, -2, -1, 0, 1, 2, -3, 4, 5] 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a tree with N vertices numbered 1 through N. The i-th of the N-1 edges connects vertices a_i and b_i.

Initially, each edge is painted blue. Takahashi will convert this blue tree into a red tree, by performing the following operation N-1 times:

* Select a simple path that consists of only blue edges, and remove one of those edges.
* Then, span a new red edge between the two endpoints of the selected path.



His objective is to obtain a tree that has a red edge connecting vertices c_i and d_i, for each i.

Determine whether this is achievable.

Constraints

* 2 ≤ N ≤ 10^5
* 1 ≤ a_i,b_i,c_i,d_i ≤ N
* a_i ≠ b_i
* c_i ≠ d_i
* Both input graphs are trees.

Input

Input is given from Standard Input in the following format:


N
a_1 b_1
:
a_{N-1} b_{N-1}
c_1 d_1
:
c_{N-1} d_{N-1}


Output

Print `YES` if the objective is achievable; print `NO` otherwise.

Examples

Input

3
1 2
2 3
1 3
3 2


Output

YES


Input

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


Output

YES


Input

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


Output

NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarpus has a complex electronic device. The core of this device is a circuit board. The board has 10^9 contact points which are numbered from 1 to 10^9. Also there are n wires numbered from 1 to n, each connecting two distinct contact points on the board. An electric signal can pass between wires A and B if: 

  * either both wires share the same contact point; 
  * or there is a sequence of wires starting with A and ending with B, and each pair of adjacent wires in the sequence share a contact point. 

<image> The picture shows a circuit board with 5 wires. Contact points with numbers 2, 5, 7, 8, 10, 13 are used. Here an electrical signal can pass from wire 2 to wire 3, but not to wire 1.

Currently the circuit board is broken. Polycarpus thinks that the board could be fixed if the wires were re-soldered so that a signal could pass between any pair of wires.

It takes 1 minute for Polycarpus to re-solder an end of a wire. I.e. it takes one minute to change one of the two contact points for a wire. Any contact point from range [1, 10^9] can be used as a new contact point. A wire's ends must always be soldered to distinct contact points. Both wire's ends can be re-solded, but that will require two actions and will take 2 minutes in total.

Find the minimum amount of time Polycarpus needs to re-solder wires so that a signal can pass between any pair of wires. Also output an optimal sequence of wire re-soldering.

Input

The input contains one or several test cases. The first input line contains a single integer t — number of test cases. Then, t test cases follow.

The first line of each test case contains a single integer n (1 ≤ n ≤ 10^5) — the number of wires. The following n lines describe wires, each line containing two space-separated integers x_i, y_i (1 ≤ x_i, y_i ≤ 10^9, x_i ≠ y_i) — contact points connected by the i-th wire. A couple of contact points can be connected with more than one wire.

Sum of values of n across all test cases does not exceed 10^5.

Output

For each test case first print one line with a single integer k — the minimum number of minutes needed to re-solder wires so that a signal can pass between any pair of wires. In the following k lines print the description of re-solderings. Each re-soldering should be described by three integers w_j, a_j, b_j (1 ≤ w_j ≤ n, 1 ≤ a_j, b_j ≤ 10^9). Such triple means that during the j-th re-soldering an end of the w_j-th wire, which was soldered to contact point a_j, becomes soldered to contact point b_j instead. After each re-soldering of a wire it must connect two distinct contact points. If there are multiple optimal re-solderings, print any of them.

Example

Input


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


Output


0
1
2 3 5

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