vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Hyperspace Jump (easy)

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The Rebel fleet is on the run. It consists of *m* ships currently gathered around a single planet. Just a few seconds ago, the vastly more powerful Empire fleet has appeared in the same solar system, and the Rebels will need to escape into hyperspace. In order to spread the fleet, the captain of each ship has independently come up with the coordinate to which that ship will jump. In the obsolete navigation system used by the Rebels, this coordinate is given as the value of an arithmetic expression of the form .

To plan the future of the resistance movement, Princess Heidi needs to know, for each ship, how many ships are going to end up at the same coordinate after the jump. You are her only hope!

Input Specification:
The first line of the input contains a single integer *m* (1<=≤<=*m*<=≤<=200<=000) – the number of ships. The next *m* lines describe one jump coordinate each, given as an arithmetic expression. An expression has the form (a+b)/c. Namely, it consists of: an opening parenthesis (, a positive integer *a* of up to two decimal digits, a plus sign +, a positive integer *b* of up to two decimal digits, a closing parenthesis ), a slash /, and a positive integer *c* of up to two decimal digits.

Output Specification:
Print a single line consisting of *m* space-separated integers. The *i*-th integer should be equal to the number of ships whose coordinate is equal to that of the *i*-th ship (including the *i*-th ship itself).

Demo Input:
['4\n(99+98)/97\n(26+4)/10\n(12+33)/15\n(5+1)/7\n']

Demo Output:
['1 2 2 1 ']

Note:
In the sample testcase, the second and the third ship will both end up at the coordinate 3.

Note that this problem has only two versions – easy and hard.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Yaroslav likes algorithms. We'll describe one of his favorite algorithms.
 1.  The algorithm receives a string as the input. We denote this input string as *a*. 1.  The algorithm consists of some number of command. Сommand number *i* looks either as *s**i* &gt;&gt; *w**i*, or as *s**i* &lt;&gt; *w**i*, where *s**i* and *w**i* are some possibly empty strings of length at most 7, consisting of digits and characters "?". 1.  At each iteration, the algorithm looks for a command with the minimum index *i*, such that *s**i* occurs in *a* as a substring. If this command is not found the algorithm terminates. 1.  Let's denote the number of the found command as *k*. In string *a* the first occurrence of the string *s**k* is replaced by string *w**k*. If the found command at that had form *s**k* &gt;&gt; *w**k*, then the algorithm continues its execution and proceeds to the next iteration. Otherwise, the algorithm terminates. 1.  The value of string *a* after algorithm termination is considered to be the output of the algorithm. 
Yaroslav has a set of *n* positive integers, he needs to come up with his favorite algorithm that will increase each of the given numbers by one. More formally, if we consider each number as a string representing the decimal representation of the number, then being run on each of these strings separately, the algorithm should receive the output string that is a recording of the corresponding number increased by one.

Help Yaroslav.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=100) — the number of elements in the set. The next *n* lines contains one positive integer each. All the given numbers are less than 1025.

Output Specification:
Print the algorithm which can individually increase each number of the set. In the *i*-th line print the command number *i* without spaces.

Your algorithm will be launched for each of these numbers. The answer will be considered correct if:   
 -  Each line will a correct algorithm command (see the description in the problem statement). -  The number of commands should not exceed 50. -  The algorithm will increase each of the given numbers by one. -  To get a respond, the algorithm will perform no more than 200 iterations for each number.

Demo Input:
['2\n10\n79\n']

Demo Output:
['10&lt;&gt;11\n79&lt;&gt;80\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Is the MRP of my new shoes exclusive or inclusive of taxes?

-----Input:-----
- First line will contain an integer $P$

-----Output:-----
For each testcase, print either 'Inclusive' or 'Exclusive' without quotes.

-----Constraints-----
- $100 \leq P \leq 999$

-----Sample Input 1:-----
123

-----Sample Output 1:-----
Exclusive

-----Sample Input 2:-----
111

-----Sample Output 2:-----
Inclusive

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Our Chef is very happy that his son was selected for training in one of the finest culinary schools of the world.
So he and his wife decide to buy a gift for the kid as a token of appreciation.
Unfortunately, the Chef hasn't been doing good business lately, and is in no mood on splurging money.
On the other hand, the boy's mother wants to buy something big and expensive.
To settle the matter like reasonable parents, they play a game.

They spend the whole day thinking of various gifts and write them down in a huge matrix.
Each cell of the matrix contains the gift's cost.
Then they decide that the mother will choose a row number r while the father will choose a column number c,
the item from the corresponding cell will be gifted to the kid in a couple of days. 

The boy observes all of this secretly.
He is smart enough to understand that his parents will ultimately choose a gift whose cost is smallest in its row,
but largest in its column.
If no such gift exists, then our little chef has no option but to keep guessing.
As the matrix is huge, he turns to you for help.

He knows that sometimes the gift is not determined uniquely even if a gift exists whose cost is smallest in its row,
but largest in its column.
However, since the boy is so smart, he realizes that the gift's cost is determined uniquely.
Your task is to tell him the gift's cost which is smallest in its row,
but largest in its column, or to tell him no such gift exists.

-----Input-----
First line contains two integers R and C, the number of rows and columns in the matrix respectively. Then follow R lines, each containing C space separated integers - the costs of different gifts.

-----Output-----
Print a single integer - a value in the matrix that is smallest in its row but highest in its column. If no such value exists, then print "GUESS" (without quotes of course) 

-----Constraints-----
1 <= R, C <= 100 
All gift costs are positive and less than 100000000 (10^8) 

-----Example 1-----
Input:
2 3
9 8 8
2 6 11

Output:
8

-----Example 2-----
Input:
3 3
9 8 11
2 6 34
5 9 11

Output:
GUESS

-----Example 3-----
Input:
2 2
10 10
10 10

Output:
10

-----Explanation of Sample Cases-----
Example 1: The first row contains 9, 8, 8. Observe that both 8 are the minimum. Considering the first 8, look at the corresponding column (containing 8 and 6). Here, 8 is the largest element in that column. So it will be chosen.
Example 2: There is no value in the matrix that is smallest in its row but largest in its column.
Example 3: The required gift in matrix is not determined uniquely, but the required cost is determined uniquely.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The goal of the 15 puzzle problem is to complete pieces on $4 \times 4$ cells where one of the cells is empty space.

In this problem, the space is represented by 0 and pieces are represented by integers from 1 to 15 as shown below.


1 2 3 4
6 7 8 0
5 10 11 12
9 13 14 15


You can move a piece toward the empty space at one step. Your goal is to make the pieces the following configuration in the shortest move (fewest steps).


1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0


Write a program which reads an initial state of the puzzle and prints the fewest steps to solve the puzzle.

Constraints

* The given puzzle is solvable in at most 45 steps.

Input

The $4 \times 4$ integers denoting the pieces or space are given.

Output

Print the fewest steps in a line.

Example

Input

1 2 3 4
6 7 8 0
5 10 11 12
9 13 14 15


Output

8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's denote a m-free matrix as a binary (that is, consisting of only 1's and 0's) matrix such that every square submatrix of size m × m of this matrix contains at least one zero. 

Consider the following problem:

You are given two integers n and m. You have to construct an m-free square matrix of size n × n such that the number of 1's in this matrix is maximum possible. Print the maximum possible number of 1's in such matrix.

You don't have to solve this problem. Instead, you have to construct a few tests for it.

You will be given t numbers x_1, x_2, ..., x_{t}. For every $i \in [ 1, t ]$, find two integers n_{i} and m_{i} (n_{i} ≥ m_{i}) such that the answer for the aforementioned problem is exactly x_{i} if we set n = n_{i} and m = m_{i}.


-----Input-----

The first line contains one integer t (1 ≤ t ≤ 100) — the number of tests you have to construct.

Then t lines follow, i-th line containing one integer x_{i} (0 ≤ x_{i} ≤ 10^9).

Note that in hacks you have to set t = 1.


-----Output-----

For each test you have to construct, output two positive numbers n_{i} and m_{i} (1 ≤ m_{i} ≤ n_{i} ≤ 10^9) such that the maximum number of 1's in a m_{i}-free n_{i} × n_{i} matrix is exactly x_{i}. If there are multiple solutions, you may output any of them; and if this is impossible to construct a test, output a single integer  - 1. 


-----Example-----
Input
3
21
0
1

Output
5 2
1 1
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Every Friday Chef and his N - 1 friends go for a party. At these parties, they play board games. This Friday, they are playing a game named "Boats! Boats! Boats!". In this game players have to transport cookies between Venice and Constantinople. Each player has a personal storage. The players are numbered from 1 to N, Chef is numbered 1. Rules for determining a winner are very difficult, therefore Chef asks you to write a program, which will determine who is a winner. 

There are 6 types of cookies. For each cookie in the storage player gets 1 point. Also player gets additional points if he packs his cookies in some boxes as follows: 

- A box containing 4 different types of cookies fetches 1 additional point.
- A box containing 5 different types of cookies fetches 2 additional points.
- A box containing 6 different types of cookies fetches 4 additional points.

Obviously a cookie can be put into a single box.

For each player, you know the number of cookies in his storage (denoted by c[i]), also the types of cookies in the storage given denoted by type[i][j].

Your task is to determine the winner of this game. Output "tie" if there are two or more players with same maximum score, "chef" if only Chef has a maximum score, winner's index in all other cases.

-----Input-----

The first line of input contains a single integer T denoting the number of test cases. This will be followed by T test cases.
The first line of each test case contains an integer N denoting the number of players.
The second line of each test case contains an integer c[i] denoting the number of cookies in the i-th storage, followed by c[i] space-separated integers type[i][j] which denote the type if j-th cookie in the storage i-th.

-----Output-----
For each test case, output a single line containing the answer as specified in the statement.

-----Constraints and Subtasks-----Subtask #1 : (20 points)  

- 1 ≤ T ≤ 10 
- 1 ≤  N  ≤ 100  
- 1 ≤  c[i]  ≤  100  
- 1 ≤  type[i][j]  ≤  3   
Subtask #2 : (80 points)  

- 1 ≤ T ≤ 10 
- 1 ≤  N  ≤ 100  
- 1 ≤  c[i]  ≤  100  
- 1 ≤  type[i][j]  ≤  6  

-----Example-----
Input:
3
2
6 1 2 3 4 5 6
9 3 3 3 4 4 4 5 5 5
2
5 2 3 4 5 6
7 1 1 2 2 3 3 4
3
4 1 1 2 3
4 1 2 2 3
4 1 2 3 3
Output:
chef
2
tie

-----Explanation-----
Example case 1.
Chef has total 6 cookie, so he gets 6 points for that. Also, he can put all his cookies (as they are all distinct) in a bag of size 6. It will fetch him additional 4 points. So, Chef's total points will be 10.
The second player has 9 cookies, he gets 9 points for that. Other than this, he can't create a bag with either 4, 5 or 6 distinct cookies. So, his final score is 9.
10 > 9 - Chef wins.
Example case 2.
Chef has 5 + 2 (a bag with 5 different cookies) = 7.
The second player has 7 + 1(a bag with 4 different cookies) = 8.
7 < 8 - the second player wins.
Example case 3.
Every player has 4 cookies and can't create any bag of sweets. So, it's a tie.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef will not be able to attend the birthday of his best friend Rock. He promised Rock that this will not be the case on his half birthday. To keep his promise Chef must know Rock’s next half birthday accurately. Being busy, he is assigning this work to you.
Half birthday is the day that occurs exactly between two subsequent birthdays. 
You will be provided with Rock’s birthdate and birth month, you will have to figure out his half birthday.
$Note$: Consider every year to be a leap year and all months are displayed in lowercase English characters.

-----Input:-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. 
- The description of each of the $T$ test cases contains an integer $d$ followed by a string, denoting month $m$.
- Here $d$ denotes day of a month and $m$ denotes the month of a year respectively.

-----Output:-----
For each test case print an integer $d1$ followed by a string, denoting month $m1$, which overall denotes date and month of Rock’s half birthday.

-----Constraints:-----
- $1 \leq T \leq 10^5$
- $1 \leq d , d1 \leq 31$
- $january \leq m , m1 \leq december$

-----Sample Input:-----
3
15 january
31 august
10 october

-----Sample Output:-----
16 july
1 march
10 april

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a multiset S. Over all pairs of subsets A and B, such that:

  * B ⊂ A; 
  * |B| = |A| - 1; 
  * greatest common divisor of all elements in A is equal to one; 



find the sum of ∑_{x ∈ A}{x} ⋅ ∑_{x ∈ B}{x}, modulo 998 244 353.

Input

The first line contains one integer m (1 ≤ m ≤ 10^5): the number of different values in the multiset S.

Each of the next m lines contains two integers a_i, freq_i (1 ≤ a_i ≤ 10^5, 1 ≤ freq_i ≤ 10^9). Element a_i appears in the multiset S freq_i times. All a_i are different.

Output

Print the required sum, modulo 998 244 353.

Examples

Input


2
1 1
2 1


Output


9


Input


4
1 1
2 1
3 1
6 1


Output


1207


Input


1
1 5


Output


560

Note

A multiset is a set where elements are allowed to coincide. |X| is the cardinality of a set X, the number of elements in it.

A ⊂ B: Set A is a subset of a set B.

In the first example B=\{1\}, A=\{1,2\} and B=\{2\}, A=\{1, 2\} have a product equal to 1⋅3 + 2⋅3=9. Other pairs of A and B don't satisfy the given constraints.

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

You bought a tree-shaped lighting fixture called a tree light.

This luminaire has n contacts, each numbered from 0 to n-1. Each contact consists of a light bulb that can express 10 levels of brightness and a device for switching the state of the light bulb. Initially, the brightness of the bulbs at all contacts is zero.

In addition, there is a cable wire between the contacts. All contacts are connected by n-1 cable lines and are hung with contact 0 facing up. Here, a set of contacts connected to the contact i via zero or more cable wires downward from the contact i is called a subtree rooted at the contact i.

You take one of the following actions with respect to this luminaire:

* count (r, x, y): Counts the number of light bulbs with a brightness of x or more and y or less among the light bulbs of the contact contained in the subtree rooted at the contact r.
* change (r, x, y): Change the brightness of all the bulbs of the contacts contained in the subtree rooted at the contact r to y, whose brightness is exactly x.



Since q actions are given, output the number of light bulbs at that time each time count (r, x, y) is given.

Constraints

* 1 ≤ n ≤ 105
* 1 ≤ q ≤ 105
* 0 ≤ ui, vi, ri ≤ n−1 (ui ≠ vi)
* 0 ≤ xi, yi ≤ 9 (when ti = 1 xi ≤ yi)

Input

The input is given in the following format.


n q
u1 v1
u2 v2
...
un−1 vn−1
t1 r1 x1 y1
t2 r2 x2 y2
...
tq rq xq yq


The number of contacts n that make up the tree light and the number of actions you take q are given on the first line, separated by blanks.
Cable line information is given on the following n-1 line, separated by blanks. The information of the i-th cable line indicates that the cable line i connects the contact ui and the contact vi with the contact ui facing up.
n & plus; The actions you take are given in the q lines after the first line, separated by blanks. If ti = 1, it represents count (ri, xi, yi), and if ti = 2, it represents change (ri, xi, yi).

Output

For each count (ri, xi, yi), output the answer on one line.

Examples

Input

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


Output

7
7
3


Input

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


Output

5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sigma and Sugim are playing a game.

The game is played on a graph with N vertices numbered 1 through N. The graph has N-1 red edges and N-1 blue edges, and the N-1 edges in each color forms a tree. The red edges are represented by pairs of integers (a_i, b_i), and the blue edges are represented by pairs of integers (c_i, d_i).

Each player has his own piece. Initially, Sigma's piece is at vertex X, and Sugim's piece is at vertex Y.

The game is played in turns, where turns are numbered starting from turn 1. Sigma takes turns 1, 3, 5, ..., and Sugim takes turns 2, 4, 6, ....

In each turn, the current player either moves his piece, or does nothing. Here, Sigma can only move his piece to a vertex that is directly connected to the current vertex by a red edge. Similarly, Sugim can only move his piece to a vertex that is directly connected to the current vertex by a blue edge.

When the two pieces come to the same vertex, the game ends immediately. If the game ends just after the operation in turn i, let i be the total number of turns in the game.

Sigma's objective is to make the total number of turns as large as possible, while Sugim's objective is to make it as small as possible.

Determine whether the game will end in a finite number of turns, assuming both players plays optimally to achieve their respective objectives. If the answer is positive, find the number of turns in the game.

Constraints

* 2 ≦ N ≦ 200,000
* 1 ≦ X, Y ≦ N
* X \neq Y
* 1 ≦ a_i, b_i, c_i, d_i ≦ N
* The N-1 edges in each color (red and blue) forms a tree.

Input

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


N X Y
a_1 b_1
a_2 b_2
:
a_{N-1} b_{N-1}
c_1 d_1
c_2 d_2
:
c_{N-1} d_{N-1}


Output

If the game will end in a finite number of turns, print the number of turns. Otherwise, print `-1`.

Examples

Input

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


Output

4


Input

3 3 1
1 2
2 3
1 2
2 3


Output

4


Input

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


Output

2


Input

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


Output

-1


Input

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


Output

6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array A of N integers. You must perform some (possibly zero) operations to make the elements of A distinct.

In one operation, you can either:
Remove one element from the beginning of the array A and append any positive integer to the end.
Or remove one element from the end of the array A and prepend any positive integer to the beginning.

Find the minimum number of operations required to make all the elements of the array distinct.

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — the size of the array A.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.

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

For each test case, output the minimum number of operations required to make all the elements distinct.

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

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 2 \cdot 10^{5}$
- The sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$

----- Sample Input 1 ------ 
3
8
1 3 3 5 1 2 4 1
4
1 2 3 4
5
10 20 10 20 30

----- Sample Output 1 ------ 
4
0
2

----- explanation 1 ------ 
Test case $1$:
Initially $A = [1, 3, 3, 5, 1, 2, 4, 1]$. Consider the following sequence of operations.
- $[1, 3, 3, 5, 1, 2, 4, \underline{1}] \xrightarrow[\mathrm{prepend} \, 6]{\mathrm{remove} \, 1} [\boldsymbol 6, 1, 3, 3, 5, 1, 2, 4]$

- $[\underline{6}, 1, 3, 3, 5, 1, 2, 4] \xrightarrow[\mathrm{append} \, 7]{\mathrm{remove} \, 6} [1, 3, 3, 5, 1, 2, 4, \boldsymbol 7]$

- $[\underline{1}, 3, 3, 5, 1, 2, 4, 7] \xrightarrow[\mathrm{append} \, 8]{\mathrm{remove} \, 1} [3, 3, 5, 1, 2, 4, 7, \boldsymbol 8]$

- $[\underline{3}, 3, 5, 1, 2, 4, 7, 8] \xrightarrow[\mathrm{append} \, 9]{\mathrm{remove} \, 3} [3, 5, 1, 2, 4, 7, 8, \boldsymbol 9]$

All the elements of $A$ are now distinct. It can be shown that it is not possible in less than $4$ operations.

Test case $2$: No operations are required since all the elements of $A$ are already distinct.

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