vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given a positive integer D. Let's build the following graph from it: 

  * each vertex is a divisor of D (not necessarily prime, 1 and D itself are also included); 
  * two vertices x and y (x > y) have an undirected edge between them if x is divisible by y and \frac x y is a prime; 
  * the weight of an edge is the number of divisors of x that are not divisors of y. 



For example, here is the graph for D=12: 

<image>

Edge (4,12) has weight 3 because 12 has divisors [1,2,3,4,6,12] and 4 has divisors [1,2,4]. Thus, there are 3 divisors of 12 that are not divisors of 4 — [3,6,12].

There is no edge between 3 and 2 because 3 is not divisible by 2. There is no edge between 12 and 3 because 12/3=4 is not a prime.

Let the length of the path between some vertices v and u in the graph be the total weight of edges on it. For example, path [(1, 2), (2, 6), (6, 12), (12, 4), (4, 2), (2, 6)] has length 1+2+2+3+1+2=11. The empty path has length 0.

So the shortest path between two vertices v and u is the path that has the minimal possible length.

Two paths a and b are different if there is either a different number of edges in them or there is a position i such that a_i and b_i are different edges.

You are given q queries of the following form: 

  * v u — calculate the number of the shortest paths between vertices v and u. 



The answer for each query might be large so print it modulo 998244353.

Input

The first line contains a single integer D (1 ≤ D ≤ 10^{15}) — the number the graph is built from.

The second line contains a single integer q (1 ≤ q ≤ 3 ⋅ 10^5) — the number of queries.

Each of the next q lines contains two integers v and u (1 ≤ v, u ≤ D). It is guaranteed that D is divisible by both v and u (both v and u are divisors of D).

Output

Print q integers — for each query output the number of the shortest paths between the two given vertices modulo 998244353.

Examples

Input


12
3
4 4
12 1
3 4


Output


1
3
1


Input


1
1
1 1


Output


1


Input


288807105787200
4
46 482955026400
12556830686400 897
414 12556830686400
4443186242880 325


Output


547558588
277147129
457421435
702277623

Note

In the first example: 

  * The first query is only the empty path — length 0; 
  * The second query are paths [(12, 4), (4, 2), (2, 1)] (length 3+1+1=5), [(12, 6), (6, 2), (2, 1)] (length 2+2+1=5) and [(12, 6), (6, 3), (3, 1)] (length 2+2+1=5). 
  * The third query is only the path [(3, 1), (1, 2), (2, 4)] (length 1+1+1=3). 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a given string S, comprising of only lowercase English alphabets, eliminate the vowels from the string that occur between two consonants(sandwiched between two immediately adjacent consonants). Print the updated string on a new line.
Example 1:
Input : S = "bab"
Output : bb
Explanation:
a is a vowel occuring between two consonants i.e. b. 
Hence the updated string eliminates a.
Example 2:
Input : S = "ceghij"
Output : cghj
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function Sandwiched_Vowel() that takes a String (s), and return the updated String. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ L ≤ 10^{5}, where L is length of string S
'a' ≤ S[i] ≤ 'z', i is an integer denoting index of S

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is making a dish that consists of exactly two ingredients. He has four ingredients A, B, C and D with tastiness a, b, c, and d respectively. He can use either A or B as the first ingredient and either C or D as the second ingredient. 

The tastiness of a dish is the sum of tastiness of its ingredients. Find the maximum possible tastiness of the dish that the chef can prepare.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- The first and only line of each test case contains four space-separated integers a, b, c, and d — the tastiness of the four ingredients.
   
------ Output Format ------ 

For each test case, output on a new line the maximum possible tastiness of the dish that chef can prepare.

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

$1 ≤ T ≤ 100$
$1 ≤ a, b, c, d ≤ 100$

----- Sample Input 1 ------ 
2
3 5 6 2
16 15 5 4

----- Sample Output 1 ------ 
11
21
----- explanation 1 ------ 
Test case $1$: Chef can prepare a dish with ingredients $B$ and $C$ with a tastiness of $5+6=11$.

Test case $2$: Chef can prepare a dish with ingredients $A$ and $C$ with a tastiness of $16+5=21$.

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

Time Limit: 1 seconds

Memory Limit: 256 megabytes

Problem Description:
The German University in Cairo (GUC) dorm houses are numbered from 1 to *n*. Underground water pipes connect these houses together. Each pipe has certain direction (water can flow only in this direction and not vice versa), and diameter (which characterizes the maximal amount of water it can handle).

For each house, there is at most one pipe going into it and at most one pipe going out of it. With the new semester starting, GUC student and dorm resident, Lulu, wants to install tanks and taps at the dorms. For every house with an outgoing water pipe and without an incoming water pipe, Lulu should install a water tank at that house. For every house with an incoming water pipe and without an outgoing water pipe, Lulu should install a water tap at that house. Each tank house will convey water to all houses that have a sequence of pipes from the tank to it. Accordingly, each tap house will receive water originating from some tank house.

In order to avoid pipes from bursting one week later (like what happened last semester), Lulu also has to consider the diameter of the pipes. The amount of water each tank conveys should not exceed the diameter of the pipes connecting a tank to its corresponding tap. Lulu wants to find the maximal amount of water that can be safely conveyed from each tank to its corresponding tap.

Input Specification:
The first line contains two space-separated integers *n* and *p* (1<=≤<=*n*<=≤<=1000,<=0<=≤<=*p*<=≤<=*n*) — the number of houses and the number of pipes correspondingly. 

Then *p* lines follow — the description of *p* pipes. The *i*-th line contains three integers *a**i* *b**i* *d**i*, indicating a pipe of diameter *d**i* going from house *a**i* to house *b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*,<=*a**i*<=≠<=*b**i*,<=1<=≤<=*d**i*<=≤<=106).

It is guaranteed that for each house there is at most one pipe going into it and at most one pipe going out of it.

Output Specification:
Print integer *t* in the first line — the number of tank-tap pairs of houses.

For the next *t* lines, print 3 integers per line, separated by spaces: *tank**i*, *tap**i*, and *diameter**i*, where *tank**i*<=≠<=*tap**i* (1<=≤<=*i*<=≤<=*t*). Here *tank**i* and *tap**i* are indexes of tank and tap houses respectively, and *diameter**i* is the maximum amount of water that can be conveyed. All the *t* lines should be ordered (increasingly) by *tank**i*.

Demo Input:
['3 2\n1 2 10\n2 3 20\n', '3 3\n1 2 20\n2 3 10\n3 1 5\n', '4 2\n1 2 60\n3 4 50\n']

Demo Output:
['1\n1 3 10\n', '0\n', '2\n1 2 60\n3 4 50\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider the number triangle below, in which each number is equal to the number above plus the number to the left. If there is no number above, assume it's a `0`.

The triangle has `5` rows and the sum of the last row is `sum([1,4,9,14,14]) = 42`.

You will be given an integer `n` and your task will be to return the sum of the last row of a triangle of `n` rows. 

In the example above:
More examples in test cases. Good luck!

```if:javascript
### Note

This kata uses native arbitrary precision integer numbers ( `BigInt`, `1n` ).  
Unfortunately, the testing framework and even native `JSON` do not fully support them yet.  
`console.log(1n)` and `(1n).toString()` work and can be used for debugging.  

We apologise for the inconvenience.
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string q. A sequence of k strings s_1, s_2, ..., s_{k} is called beautiful, if the concatenation of these strings is string q (formally, s_1 + s_2 + ... + s_{k} = q) and the first characters of these strings are distinct.

Find any beautiful sequence of strings or determine that the beautiful sequence doesn't exist.


-----Input-----

The first line contains a positive integer k (1 ≤ k ≤ 26) — the number of strings that should be in a beautiful sequence. 

The second line contains string q, consisting of lowercase Latin letters. The length of the string is within range from 1 to 100, inclusive.


-----Output-----

If such sequence doesn't exist, then print in a single line "NO" (without the quotes). Otherwise, print in the first line "YES" (without the quotes) and in the next k lines print the beautiful sequence of strings s_1, s_2, ..., s_{k}.

If there are multiple possible answers, print any of them.


-----Examples-----
Input
1
abca

Output
YES
abca

Input
2
aaacas

Output
YES
aaa
cas

Input
4
abc

Output
NO



-----Note-----

In the second sample there are two possible answers: {"aaaca", "s"} and {"aaa", "cas"}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function that accepts an array of 10 integers (between 0 and 9), that returns a string of those numbers in the form of a phone number.

Example:

```python
create_phone_number([1, 2, 3, 4, 5, 6, 7, 8, 9, 0]) # => returns "(123) 456-7890"
```
```f#
createPhoneNumber [1; 2; 3; 4; 5; 6; 7; 8; 9; 0] // => returns "(123) 456-7890"
```

The returned format must be correct in order to complete this challenge. 
Don't forget the space after the closing parentheses!

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
To confuse the opponents, the Galactic Empire represents fractions in an unusual format. The fractions are represented as two sets of integers. The product of numbers from the first set gives the fraction numerator, the product of numbers from the second set gives the fraction denominator. However, it turned out that the programs that work with fractions in this representations aren't complete, they lack supporting the operation of reducing fractions. Implement this operation and the Empire won't forget you.

Input Specification:
The first input line contains two space-separated integers *n*, *m* (1<=≤<=*n*,<=*m*<=≤<=105) that show how many numbers the first set (the numerator) and the second set (the denominator) contain, correspondingly.

The second line contains *n* space-separated integers: *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=107) — the numbers that are multiplied to produce the numerator.

The third line contains *m* space-separated integers: *b*1,<=*b*2,<=...,<=*b**m* (1<=≤<=*b**i*<=≤<=107) — the numbers that are multiplied to produce the denominator.

Output Specification:
Print the answer to the problem in the form, similar to the form of the input data. The number of values in the sets you print *n**out*,<=*m**out* must satisfy the inequality 1<=≤<=*n**out*,<=*m**out*<=≤<=105, and the actual values in the sets *a**out*,<=*i* and *b**out*,<=*i* must satisfy the inequality 1<=≤<=*a**out*,<=*i*,<=*b**out*,<=*i*<=≤<=107. 

Separate the values in the lines by spaces. The printed fraction must be reduced, that is, there mustn't be such integer *x* (*x*<=&gt;<=1), that the numerator and the denominator of the printed fraction are divisible by *x*. If there are several matching answers, print any of them.

Demo Input:
['3 2\n100 5 2\n50 10\n', '4 3\n2 5 10 20\n100 1 3\n']

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

Note:
In the first test sample the numerator equals 1000, the denominator equals 500. If we reduce fraction 1000/500 by the greatest common divisor of the numerator and the denominator (by 500), we obtain fraction 2/1.

In the second test sample the numerator equals 2000, the denominator equals 300. If we reduce fraction 2000/300 by the greatest common divisor of the numerator and the denominator (by 100), we obtain fraction 20/3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You come home and fell some unpleasant smell. Where is it coming from?

You are given an array a. You have to answer the following queries: 

  1. You are given two integers l and r. Let ci be the number of occurrences of i in al: r, where al: r is the subarray of a from l-th element to r-th inclusive. Find the Mex of {c0, c1, ..., c109}
  2. You are given two integers p to x. Change ap to x. 



The Mex of a multiset of numbers is the smallest non-negative integer not in the set.

Note that in this problem all elements of a are positive, which means that c0 = 0 and 0 is never the answer for the query of the second type.

Input

The first line of input contains two integers n and q (1 ≤ n, q ≤ 100 000) — the length of the array and the number of queries respectively.

The second line of input contains n integers — a1, a2, ..., an (1 ≤ ai ≤ 109).

Each of the next q lines describes a single query.

The first type of query is described by three integers ti = 1, li, ri, where 1 ≤ li ≤ ri ≤ n — the bounds of the subarray.

The second type of query is described by three integers ti = 2, pi, xi, where 1 ≤ pi ≤ n is the index of the element, which must be changed and 1 ≤ xi ≤ 109 is the new value.

Output

For each query of the first type output a single integer — the Mex of {c0, c1, ..., c109}.

Example

Input

10 4
1 2 3 1 1 2 2 2 9 9
1 1 1
1 2 8
2 7 1
1 2 8


Output

2
3
2

Note

The subarray of the first query consists of the single element — 1. 

The subarray of the second query consists of four 2s, one 3 and two 1s.

The subarray of the fourth query consists of three 1s, three 2s and one 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
John, a student who is taking the game development course, recently developed a mobile game called Fruit Slicer for his coursework. In the game the player slices fruits that are throw into the air by swiping the touch screen. However the game is quite simple because John was not able to write code for the geometry required for a more complex version. In the game each slice is a straight line of infinite length, and all fruits have the same shape of a circle with unit radius. The figure shows a cool snapshot of John’s game. 

John introduces his game to his best friend Sean, who soon gets bored of playing the simple game. But as a teaching assistant of the algorithm course, Sean decides to turn the game into a homework assignment. He asks the students in the algorithms course to write a program that can compute the best slice at any given moment of the game. Given the locations of the fruits, the program should determine the maximum number of fruits that can be sliced with a single straight-line swipe.

As a student in Sean’s class, you are now the one who is facing this challenge.

-----Input-----
The first line has a single integer $n$ ($1 \leq n \leq 100$). The next $n$ lines each have two real numbers giving the $x$ and $y$ coordinates of a fruit. All coordinates have an absolute value no larger than $10^4$ and are given with exactly two digits after the decimal point. Fruits may overlap.

-----Output-----
Output the maximum number of fruits that can be sliced with one straight-line swipe. A swipe slices a fruit if the line intersects the inner part or the boundary of the fruit.

-----Examples-----
Sample Input 1:
5
1.00 5.00
3.00 3.00
4.00 2.00
6.00 4.50
7.00 1.00
Sample Output 1:
4

Sample Input 2:
3
-1.50 -1.00
1.50 -1.00
0.00 1.00
Sample Output 2:
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Reforms continue entering Berland. For example, during yesterday sitting the Berland Parliament approved as much as n laws (each law has been assigned a unique number from 1 to n). Today all these laws were put on the table of the President of Berland, G.W. Boosch, to be signed.

This time mr. Boosch plans to sign 2k laws. He decided to choose exactly two non-intersecting segments of integers from 1 to n of length k and sign all laws, whose numbers fall into these segments. More formally, mr. Boosch is going to choose two integers a, b (1 ≤ a ≤ b ≤ n - k + 1, b - a ≥ k) and sign all laws with numbers lying in the segments [a; a + k - 1] and [b; b + k - 1] (borders are included).

As mr. Boosch chooses the laws to sign, he of course considers the public opinion. Allberland Public Opinion Study Centre (APOSC) conducted opinion polls among the citizens, processed the results into a report and gave it to the president. The report contains the absurdity value for each law, in the public opinion. As mr. Boosch is a real patriot, he is keen on signing the laws with the maximum total absurdity. Help him.


-----Input-----

The first line contains two integers n and k (2 ≤ n ≤ 2·10^5, 0 < 2k ≤ n) — the number of laws accepted by the parliament and the length of one segment in the law list, correspondingly. The next line contains n integers x_1, x_2, ..., x_{n} — the absurdity of each law (1 ≤ x_{i} ≤ 10^9).


-----Output-----

Print two integers a, b — the beginning of segments that mr. Boosch should choose. That means that the president signs laws with numbers from segments [a; a + k - 1] and [b; b + k - 1]. If there are multiple solutions, print the one with the minimum number a. If there still are multiple solutions, print the one with the minimum b.


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

Output
1 4

Input
6 2
1 1 1 1 1 1

Output
1 3



-----Note-----

In the first sample mr. Boosch signs laws with numbers from segments [1;2] and [4;5]. The total absurdity of the signed laws equals 3 + 6 + 1 + 6 = 16.

In the second sample mr. Boosch signs laws with numbers from segments [1;2] and [3;4]. The total absurdity of the signed laws equals 1 + 1 + 1 + 1 = 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A rare article in the Internet is posted without a possibility to comment it. On a Polycarp's website each article has comments feed.

Each comment on Polycarp's website is a non-empty string consisting of uppercase and lowercase letters of English alphabet. Comments have tree-like structure, that means each comment except root comments (comments of the highest level) has exactly one parent comment.

When Polycarp wants to save comments to his hard drive he uses the following format. Each comment he writes in the following format: 

  * at first, the text of the comment is written; 
  * after that the number of comments is written, for which this comment is a parent comment (i. e. the number of the replies to this comments); 
  * after that the comments for which this comment is a parent comment are written (the writing of these comments uses the same algorithm). 

All elements in this format are separated by single comma. Similarly, the comments of the first level are separated by comma.

For example, if the comments look like:

<image>

then the first comment is written as "hello,2,ok,0,bye,0", the second is written as "test,0", the third comment is written as "one,1,two,2,a,0,b,0". The whole comments feed is written as: "hello,2,ok,0,bye,0,test,0,one,1,two,2,a,0,b,0". For a given comments feed in the format specified above print the comments in a different format: 

  * at first, print a integer d — the maximum depth of nesting comments; 
  * after that print d lines, the i-th of them corresponds to nesting level i; 
  * for the i-th row print comments of nesting level i in the order of their appearance in the Policarp's comments feed, separated by space. 

Input

The first line contains non-empty comments feed in the described format. It consists of uppercase and lowercase letters of English alphabet, digits and commas. 

It is guaranteed that each comment is a non-empty string consisting of uppercase and lowercase English characters. Each of the number of comments is integer (consisting of at least one digit), and either equals 0 or does not contain leading zeros.

The length of the whole string does not exceed 106. It is guaranteed that given structure of comments is valid. 

Output

Print comments in a format that is given in the statement. For each level of nesting, comments should be printed in the order they are given in the input.

Examples

Input

hello,2,ok,0,bye,0,test,0,one,1,two,2,a,0,b,0


Output

3
hello test one 
ok bye two 
a b 


Input

a,5,A,0,a,0,A,0,a,0,A,0


Output

2
a 
A a A a A 


Input

A,3,B,2,C,0,D,1,E,0,F,1,G,0,H,1,I,1,J,0,K,1,L,0,M,2,N,0,O,1,P,0


Output

4
A K M 
B F H L N O 
C D G I P 
E J 

Note

The first example is explained in the statements. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Probably you all are familiar with famous tiles problem in which you have to fill 2*n size field using tiles of size 2*1. Now consider that same 2*n size field is composed of 1*1 size cells. So there are total 2*n cells in field. Now we will fill that field with tiles randomly. There would be
a number of ways in which we can fill that field using these tiles ( Actually in classic version of problem, we count the no of ways). Now assume that when a tile is 
put vertically in the field (for example when tile is placed covering cell no (1,1) and (2,1)), it adds a weight of 1 unit each on both cells. But when a tile is 
placed horizontally ( for example when tile is placed covering cell no (1,1) and (1,2)), it doesn't add any weight on any cell. Now as you know there are a lot of 
ways to fill a 2*n size field, in some ways there can be weight on some particular cell, in some other ways there might not be weight on that particular cell 
(depending upon whether the tile covering that particular cell is horizontal or vertical). So there will be some expected value of weight on every cell when you will
fill a 2*n size field randomly. You have to calculate expected value of weight on every cell and find their sum. So you will be given 'n' in input and you have to output desired 
sum of expected value of weight on each cell.

Ex: If n=2, then there are two ways to arrange tiles. In one way both tiles will be horizontal and in other both are vertical. Let four cells are
(1,1), (1,2), (2,1), (2,2). So in first method there will be '0' weight on each cell and in second there will be '1' weight on each cell. So for every cell
expected value of weight is 0.5 , so sum of all four cell will be 0.5 * 4 = 2.

Input: First line will contain 't', number of test cases. 't' lines follow, each containing value of n.

Output: For each test case output the sum of expected weight on each cell (answer must be correct upto 6 decimal places).

Constraints: 

1 ≤ t ≤ 1000

1 ≤ n ≤ 50

SAMPLE INPUT
4
1
2
3
4

SAMPLE OUTPUT
2.000000
2.000000
3.333333
4.000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your task is to make two functions, ```max``` and ```min``` (`maximum` and `minimum` in PHP and Python) that take a(n) array/vector of integers ```list``` as input and outputs, respectively, the largest and lowest number in that array/vector.

#Examples
```python
maximun([4,6,2,1,9,63,-134,566]) returns 566
minimun([-52, 56, 30, 29, -54, 0, -110]) returns -110
maximun([5]) returns 5
minimun([42, 54, 65, 87, 0]) returns 0
```

#Notes
- You may consider that there will not be any empty arrays/vectors.

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