vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Find the minimum number with the given sum of digits $s$ such that all digits in it are distinct (i.e. all digits are unique).

For example, if $s=20$, then the answer is $389$. This is the minimum number in which all digits are different and the sum of the digits is $20$ ($3+8+9=20$).

For the given $s$ print the required number.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 45$) — the number of test cases.

Each test case is specified by a line that contains the only integer $s$ ($1 \le s \le 45$).


-----Output-----

Print $t$ integers — the answers to the given test cases.


-----Examples-----

Input
4
20
8
45
10
Output
389
8
123456789
19


-----Note-----

None

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: War of the Corporations

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A long time ago, in a galaxy far far away two giant IT-corporations Pineapple and Gogol continue their fierce competition. Crucial moment is just around the corner: Gogol is ready to release it's new tablet Lastus 3000.

This new device is equipped with specially designed artificial intelligence (AI). Employees of Pineapple did their best to postpone the release of Lastus 3000 as long as possible. Finally, they found out, that the name of the new artificial intelligence is similar to the name of the phone, that Pineapple released 200 years ago. As all rights on its name belong to Pineapple, they stand on changing the name of Gogol's artificial intelligence.

Pineapple insists, that the name of their phone occurs in the name of AI as a substring. Because the name of technology was already printed on all devices, the Gogol's director decided to replace some characters in AI name with "#". As this operation is pretty expensive, you should find the minimum number of characters to replace with "#", such that the name of AI doesn't contain the name of the phone as a substring.

Substring is a continuous subsequence of a string.

Input Specification:
The first line of the input contains the name of AI designed by Gogol, its length doesn't exceed 100<=000 characters. Second line contains the name of the phone released by Pineapple 200 years ago, its length doesn't exceed 30. Both string are non-empty and consist of only small English letters.

Output Specification:
Print the minimum number of characters that must be replaced with "#" in order to obtain that the name of the phone doesn't occur in the name of AI as a substring.

Demo Input:
['intellect\ntell\n', 'google\napple\n', 'sirisiri\nsir\n']

Demo Output:
['1', '0', '2']

Note:
In the first sample AI's name may be replaced with "int#llect".

In the second sample Gogol can just keep things as they are.

In the third sample one of the new possible names of AI may be "s#ris#ri".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two integers A and B are the inputs. Write a program to find GCD and LCM of A and B.

-----Input-----

The first line contains an integer T, total number of testcases. Then follow T lines, each line contains an integer A and B. 

-----Output-----
Display the GCD and LCM of A and B separated by space respectively. The answer for each test case must be displayed in a new line.

-----Constraints-----
- 1 ≤ T ≤ 1000
- 1 ≤ A,B ≤ 1000000

-----Example-----
Input
3 
120 140
10213 312
10 30

Output

20 840
1 3186456
10 30

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
-----
ARRAY AND DISTINCT ELEMENTS
-----

Chef is multitalented but he mistakenly took part in 2 contest which will take place
at the same time. So while chef is busy at one cooking contest, he wants you to
take part in coding contest. Chef wants u to solve this program for him.

	

You have been given an array of size n. You have to calculate a subarray of size k
with maximum sum having distinct elements same as original array.

		
		

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

First line contains no. of test cases. Second line contains n and k. Third line
contains array of n integers.


-----Output-----

Print maximum possible sum as stated in question

		
		

-----Example Text Case-----
Input:

1
10 6
8 8 3 5 3 8 5 7 7 7

Output:
37

		

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have an empty sequence, and you will be given $N$ queries. Each query is one of these three types:

1 x  -Push the element x into the stack.
2    -Delete the element present at the top of the stack.
3    -Print the maximum element in the stack.

Function Description  

Complete the getMax function in the editor below.   

getMax has the following parameters: 

- string operations[n]: operations as strings   

Returns 

- int[]: the answers to each type 3 query   

Input Format

The first line of input contains an integer, $n$. The next $n$ lines each contain an above mentioned query.   

Constraints

Constraints 

$1\leq n\leq10^5$ 

$1\leq x\leq10^9$ 

$1\leq type\leq3$ 

All queries are valid.  

Sample Input
STDIN   Function
-----   --------
10      operations[] size n = 10
1 97    operations = ['1 97', '2', '1 20', ....]
2
1 20
2
1 26
1 20
2
3
1 91
3

Sample Output
26
91

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Sheokand loves strings. Chef has $N$ strings $S_{1}, S_{2}, \dots, S_{N}$ which he wants to give to Sheokand; however, he doesn't want to give them away for free, so Sheokand must first correctly answer $Q$ queries Chef asks him.

In each query, Chef tells Sheokand an integer $R$ and a string $P$. Consider Chef's strings $S_{1}$ through $S_{R}$. Out of these strings, consider all strings such that their longest common prefix with $P$ is maximum possible. Sheokand should find the lexicographically smallest of these strings.

Sheokand is busy with his exams. Can you solve the queries for him?

------  Input ------
The first line of the input contains a single integer $N$.
$N$ lines follow. For each valid $i$, the $i$-th of these lines contains Chef's string $S_{i}$.
The next line contains a single integer $Q$.
The following $Q$ lines describe queries. Each of these lines contains an interger $R$, followed by a space and a string $P$.

------  Output ------
For each query, print a single line containing the string that satisfies the required conditions — the answer to that query.

------  Constraints  ------
$1 ≤ N ≤ 100,000$ 
$1 ≤ |S_{i}| ≤ 10$ for each valid $i$
$1 ≤ Q ≤ 100,000$
$1 ≤ R ≤ N$
$1 ≤ |P| ≤ 10$

------  Subtasks ------
Subtask #1 (30 points): $1 ≤ N, R ≤ 1,000$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
4
abcd
abce
abcdex
abcde
3
3 abcy
3 abcde
4 abcde
----- Sample Output 1 ------ 
abcd
abcdex
abcde
----- explanation 1 ------ 
Query 1: For strings $S_{1}$ through $S_{3}$, the longest common prefix is always "abc", but "abcd" is the lexicographically smallest of these three strings.

Query 2: For strings $S_{1}$ through $S_{3}$, the longest common prefix with maximum length is "abcde" and the only string for which it is the LCP is "abcdex", so this is the answer.

Query 3: For strings $S_{1}$ through $S_{4}$, the longest common prefix with maximum length is "abcde"; it is the LCP for strings "abcdex" and "abcde", but "abcde" is the lexicographically smaller string, so it is the answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Note : This question carries $100$ $points$
CodeLand is celebrating a festival by baking cakes! In order to avoid wastage, families follow a unique way of distributing cakes.
For $T$ families in the locality, $i$-th family (1 <= $i$ <= $T$) has $N$ members. They baked $S$ slices of cakes. The smallest member of the family gets $K$ slices of cakes. Each family has a lucky number of $R$ and they agree to distribute the slices such that the member gets $R$ times more slices than the member just smaller than them. Since the family is busy in festival preparations, find out if the number of slices would be sufficient for the family or not. Also, find how many extra slices they have or how many slices are they short of.
Also, the locality is kind and believes in sharing. So, you also need to determine if each family would have sufficient slices if families shared their cakes among each other!

-----Input :-----
- First line of input will have a single integer $T$ i.e. the number of families in the locality
- For next $T$ lines, each line will describe one family through 4 integers i.e. $S$, $N$, $K$, $R$ separated by spaces

-----Output-----
- First $T$ lines of output will show if slices are enough for the family or not, followed by extra or required slices. For example, if slices are sufficient, the output would be $POSSIBLE$ $10$ which implies 10 slices are extra. If slices are insufficient, the output would be $IMPOSSIBLE$ $15$ which implies 15 slices are required to fulfill the requirement.
- Last line of output would be $IMPOSSIBLE$ or $POSSIBLE$ depending on whether each family would get enough slices after sharing.

-----Constraints:-----
- 1 ≤ $T$ ≤ 50
- 1 ≤ $N$ ≤ 15
- 1 ≤ $S$ ≤ 10^9
- 1 ≤ $K$ ≤ 5
- 1 ≤ $R$ ≤ 5

-----Sample Input:-----
5
100 4 2 2
100 4 3 2
100 4 3 3
200 4 4 2
10 3 2 2

-----Sample Output:-----
POSSIBLE 70
POSSIBLE 55
IMPOSSIBLE 20
POSSIBLE 140
IMPOSSIBLE 4
POSSIBLE

-----Explanation-----
For the first home, the youngest member has got 2 slices, the one older than them gets 2 times more slices, and so forth. So, first home needs 2 + 4 + 8 + 16 = 30 slices. But since they made 100, they have 70 extra, hence we print 'POSSIBLE 70'.
Doing the same for other houses, we find 20 + 4 = 24 slices extra are required so that all families have enough slices. In this case we have 70 + 55 + 140 = 265 extra slices which is > 24, so we print 'POSSIBLE' in last line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
I'm traveling to a country with a rabbit. There are n cities in this country numbered from 1 to n, and the rabbit is now in city 1. City i is a point on the coordinate plane (xi, yi) ).

Rabbits travel to meet the following conditions.

* The travel path is a polygonal line, each part of which must be a line segment connecting two different cities.
* The total length of the travel route must be r or less. The overlapping part of the route is also counted for the number of times it has passed.
* When the direction of movement changes, the bending angle must be less than or equal to θ. There is no limit to the initial direction of movement.



If you move from one city to another, you will get one carrot in the destination city. You can visit the same city multiple times, and you will get a carrot each time you visit. Find the maximum number of carrots you can put in.



Input

One integer n is given on the first line of the input, and two real numbers r and θ are given on the second line, separated by a space.

1 ≤ n ≤ 20
0 <r <104
0 ° <θ <180 °


The following n lines are given the integers xi and yi separated by spaces.

-10 000 ≤ xi, yi ≤ 10 000

The answer does not change even if r and θ are changed within ± 10-3.
The locations of both cities are different.

Output

Output the maximum number of carrots that the rabbit can get on this trip in one line.

Example

Input

5
100.1 90.1
0 0
0 10
5 5
10 0
10 10


Output

10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Dogeforces company has $k$ employees. Each employee, except for lower-level employees, has at least $2$ subordinates. Lower-level employees have no subordinates. Each employee, except for the head of the company, has exactly one direct supervisor. The head of the company is a direct or indirect supervisor of all employees. It is known that in Dogeforces, each supervisor receives a salary strictly more than all his subordinates.

The full structure of the company is a secret, but you know the number of lower-level employees and for each pair of lower-level employees, the salary of their common supervisor is known (if there are several such supervisors, then the supervisor with the minimum salary). You have to restore the structure of the company.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 500$) — the number of lower-level employees.

This is followed by $n$ lines, where $i$-th line contains $n$ integers $a_{i,1}, a_{i,2}, \dots, a_{i,n}$ ($1 \le a_{i,j} \le 5000$) — salary of the common supervisor of employees with numbers $i$ and $j$. It is guaranteed that $a_{i,j} = a_{j,i}$. Note that $a_{i,i}$ is equal to the salary of the $i$-th employee.


-----Output-----

In the first line, print a single integer $k$ — the number of employees in the company.

In the second line, print $k$ integers $c_1, c_2, \dots, c_k$, where $c_i$ is the salary of the employee with the number $i$.

In the third line, print a single integer $r$ — the number of the employee who is the head of the company.

In the following $k-1$ lines, print two integers $v$ and $u$ ($1 \le v, u \le k$) — the number of the employee and his direct supervisor.

Note that the lower-level employees have numbers from $1$ to $n$, and for the rest of the employees, you have to assign numbers from $n+1$ to $k$. If there are several correct company structures, you can print any of them.


-----Examples-----

Input
3
2 5 7
5 1 7
7 7 4
Output
5
2 1 4 7 5 
4
1 5
2 5
5 4
3 4


-----Note-----

One of the possible structures in the first example:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Allen and Bessie are playing a simple number game. They both know a function f: \{0, 1\}^n → R, i. e. the function takes n binary arguments and returns a real value. At the start of the game, the variables x_1, x_2, ..., x_n are all set to -1. Each round, with equal probability, one of Allen or Bessie gets to make a move. A move consists of picking an i such that x_i = -1 and either setting x_i → 0 or x_i → 1.

After n rounds all variables are set, and the game value resolves to f(x_1, x_2, ..., x_n). Allen wants to maximize the game value, and Bessie wants to minimize it.

Your goal is to help Allen and Bessie find the expected game value! They will play r+1 times though, so between each game, exactly one value of f changes. In other words, between rounds i and i+1 for 1 ≤ i ≤ r, f(z_1, ..., z_n) → g_i for some (z_1, ..., z_n) ∈ \{0, 1\}^n. You are to find the expected game value in the beginning and after each change.

Input

The first line contains two integers n and r (1 ≤ n ≤ 18, 0 ≤ r ≤ 2^{18}).

The next line contains 2^n integers c_0, c_1, ..., c_{2^n-1} (0 ≤ c_i ≤ 10^9), denoting the initial values of f. More specifically, f(x_0, x_1, ..., x_{n-1}) = c_x, if x = \overline{x_{n-1} … x_0} in binary.

Each of the next r lines contains two integers z and g (0 ≤ z ≤ 2^n - 1, 0 ≤ g ≤ 10^9). If z = \overline{z_{n-1} ... z_0} in binary, then this means to set f(z_0, ..., z_{n-1}) → g.

Output

Print r+1 lines, the i-th of which denotes the value of the game f during the i-th round. Your answer must have absolute or relative error within 10^{-6}.

Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if \frac{|a - b|}{max{(1, |b|)}} ≤ 10^{-6}.

Examples

Input

2 2
0 1 2 3
2 5
0 4


Output

1.500000
2.250000
3.250000


Input

1 0
2 3


Output

2.500000


Input

2 0
1 1 1 1


Output

1.000000

Note

Consider the second test case. If Allen goes first, he will set x_1 → 1, so the final value will be 3. If Bessie goes first, then she will set x_1 → 0 so the final value will be 2. Thus the answer is 2.5.

In the third test case, the game value will always be 1 regardless of Allen and Bessie's play.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are a lot of rumors in the media these days. One day Aida decided to find out how rumors are made.

She asked n of her friends to help her. They all formed a circle and Aida told the person to her right a piece of news which was just a simple string. Then each person told the string to the person on his/her right. But they didn't tell the string exactly as they'd heard it. Each person made at most one of these two types of changes: 

  * Removing one character from the end of the heard string. 
  * Adding a character to the end of the heard string. 



Finally when the rumor passed exactly n moves (a complete cycle), Aida heard something quite different from what she expected from the person on her left. She thinks someone has cheated and made some changes other than those explained above. Now she wants you to write a Pike piece of code which gets the initial and final strings and tells Aida whether it's possible to get to the final string from the initial one, by the rules described above.

Input

The first line contains a single integer n (2 ≤ n ≤ 8 × 106), the number of Aida's friends. The following two lines contain a non-empty string each — initial and final strings. The lengths of strings are at most 107 and they only contain English alphabet letters.

Output

Write a single YES or NO. Write YES only if it's possible to get to the final string from the initial string.

Examples

Input

100
Codeforces
MMIODPC


Output

Yes


Input

5
MMIOD
CF


Output

No

Note

The input is case-sensitive, while the output is not.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It is the year 2969. 1000 years have passed from the moon landing. Meanwhile, the humanity colonized the Hyperspace™ and lived in harmony.

Until we realized that we were not alone.

Not too far away from the Earth, the massive fleet of aliens' spaceships is preparing to attack the Earth. For the first time in a while, the humanity is in real danger. Crisis and panic are everywhere. The scientists from all around the solar system have met and discussed the possible solutions. However, no progress has been made.

The Earth's last hope is YOU!

Fortunately, the Earth is equipped with very powerful defense systems made by MDCS. There are N aliens' spaceships which form the line. The defense system consists of three types of weapons: 

  * SQL rockets – every SQL rocket can destroy at most one spaceship in the given set.
  * Cognition beams – every Cognition beam has an interval [l,r] and can destroy at most one spaceship in that interval.
  * OMG bazooka – every OMG bazooka has three possible targets, however, each bazooka can destroy either zero or exactly two spaceships. In addition, due to the smart targeting system, the sets of the three possible targets of any two different OMG bazookas are disjoint (that means that every ship is targeted with at most one OMG bazooka). 



Your task is to make a plan of the attack which will destroy the largest possible number of spaceships. Every destroyed spaceship should be destroyed with exactly one weapon.

Input

The first line contains two integers: the number of your weapons N (1≤ N≤ 5000) and the number of spaceships M (1≤ M≤ 5000).

In the next N lines, each line starts with one integer that represents type (either 0, 1 or 2). If the type is 0, then the weapon is SQL rocket, the rest of the line contains strictly positive number K (∑{K} ≤ 100 000) and array k_i (1≤ k_i≤ M) of K integers. If the type is 1, then the weapon is Cognition beam, the rest of the line contains integers l and r (1≤ l≤ r≤ M). If the type is 2 then the weapon is OMG bazooka, the rest of the line contains distinct numbers a, b and c  (1 ≤ a,b,c ≤ M).

Output

The first line should contain the maximum number of destroyed spaceships — X.

In the next X lines, every line should contain two numbers A and B, where A is an index of the weapon and B is an index of the spaceship which was destroyed by the weapon A.

Example

Input

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


Output

4
2 1
3 2
1 4
2 5

Note

SQL rocket can destroy only 4th spaceship. OMG Bazooka can destroy two of 1st, 4th or 5th spaceship, and Cognition beam can destroy any spaceship from the interval [1,4]. The maximum number of destroyed spaceship is 4, and one possible plan is that SQL rocket should destroy 4th spaceship, OMG bazooka should destroy 1st and 5th spaceship and Cognition beam should destroy 2nd spaceship.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As we all know, Chef is cooking string for long days, his new discovery on string is the longest common pattern length. The longest common pattern length between two strings is the maximum number of characters that both strings have in common. Characters are case sensitive, that is, lower case and upper case characters are considered as different. Note that characters can repeat in a string and a character might have one or more occurrence in common between two strings. For example, if Chef has two strings A = "Codechef" and B = "elfedcc", then the longest common pattern length of A and B is 5 (common characters are c, d, e, e, f).
Chef wants to test you with the problem described above. He will give you two strings of Latin alphabets and digits, return him the longest common pattern length.

-----Input-----
The first line of the input contains an integer T, denoting the number of test cases. Then the description of T test cases follows.
The first line of each test case contains a string A. The next line contains another character string B.

-----Output-----
For each test case, output a single line containing a single integer, the longest common pattern length between A and B.

-----Constraints-----
- 1 ≤ T ≤ 100
- 1 ≤ |A|, |B| ≤ 10000 (104), where |S| denotes the length of the string S
- Both of A and B can contain only alphabet characters (both lower and upper case) and digits

-----Example-----
Input:
4
abcd
xyz
abcd
bcda
aabc
acaa
Codechef
elfedcc

Output:
0
4
3
5

-----Explanation-----
Example case 1. There is no common character.
Example case 2. All the characters are same.
Example case 3. Three characters (a, a and c) are same.
Example case 4. This sample is mentioned by the statement.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An undirected graph is called k-regular, if the degrees of all its vertices are equal k. An edge of a connected graph is called a bridge, if after removing it the graph is being split into two connected components.

Build a connected undirected k-regular graph containing at least one bridge, or else state that such graph doesn't exist.

Input

The single line of the input contains integer k (1 ≤ k ≤ 100) — the required degree of the vertices of the regular graph.

Output

Print "NO" (without quotes), if such graph doesn't exist. 

Otherwise, print "YES" in the first line and the description of any suitable graph in the next lines.

The description of the made graph must start with numbers n and m — the number of vertices and edges respectively. 

Each of the next m lines must contain two integers, a and b (1 ≤ a, b ≤ n, a ≠ b), that mean that there is an edge connecting the vertices a and b. A graph shouldn't contain multiple edges and edges that lead from a vertex to itself. A graph must be connected, the degrees of all vertices of the graph must be equal k. At least one edge of the graph must be a bridge. You can print the edges of the graph in any order. You can print the ends of each edge in any order.

The constructed graph must contain at most 106 vertices and 106 edges (it is guaranteed that if at least one graph that meets the requirements exists, then there also exists the graph with at most 106 vertices and at most 106 edges). 

Examples

Input

1


Output

YES
2 1
1 2

Note

In the sample from the statement there is a suitable graph consisting of two vertices, connected by a single edge.

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