vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
We saw the little game Marmot made for Mole's lunch. Now it's Marmot's dinner time and, as we all know, Marmot eats flowers. At every dinner he eats some red and white flowers. Therefore a dinner can be represented as a sequence of several flowers, some of them white and some of them red.

But, for a dinner to be tasty, there is a rule: Marmot wants to eat white flowers only in groups of size k.

Now Marmot wonders in how many ways he can eat between a and b flowers. As the number of ways could be very large, print it modulo 1000000007 (10^9 + 7).


-----Input-----

Input contains several test cases.

The first line contains two integers t and k (1 ≤ t, k ≤ 10^5), where t represents the number of test cases.

The next t lines contain two integers a_{i} and b_{i} (1 ≤ a_{i} ≤ b_{i} ≤ 10^5), describing the i-th test.


-----Output-----

Print t lines to the standard output. The i-th line should contain the number of ways in which Marmot can eat between a_{i} and b_{i} flowers at dinner modulo 1000000007 (10^9 + 7).


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

Output
6
5
5



-----Note-----  For K = 2 and length 1 Marmot can eat (R).  For K = 2 and length 2 Marmot can eat (RR) and (WW).  For K = 2 and length 3 Marmot can eat (RRR), (RWW) and (WWR).  For K = 2 and length 4 Marmot can eat, for example, (WWWW) or (RWWR), but for example he can't eat (WWWR).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n houses in a row. They are numbered from 1 to n in order from left to right. Initially you are in the house 1.

You have to perform k moves to other house. In one move you go from your current house to some other house. You can't stay where you are (i.e., in each move the new house differs from the current house). If you go from the house x to the house y, the total distance you walked increases by |x-y| units of distance, where |a| is the absolute value of a. It is possible to visit the same house multiple times (but you can't visit the same house in sequence).

Your goal is to walk exactly s units of distance in total.

If it is impossible, print "NO". Otherwise print "YES" and any of the ways to do that. Remember that you should do exactly k moves.

Input

The first line of the input contains three integers n, k, s (2 ≤ n ≤ 10^9, 1 ≤ k ≤ 2 ⋅ 10^5, 1 ≤ s ≤ 10^{18}) — the number of houses, the number of moves and the total distance you want to walk.

Output

If you cannot perform k moves with total walking distance equal to s, print "NO".

Otherwise print "YES" on the first line and then print exactly k integers h_i (1 ≤ h_i ≤ n) on the second line, where h_i is the house you visit on the i-th move.

For each j from 1 to k-1 the following condition should be satisfied: h_j ≠ h_{j + 1}. Also h_1 ≠ 1 should be satisfied.

Examples

Input

10 2 15


Output

YES
10 4 


Input

10 9 45


Output

YES
10 1 10 1 2 1 2 1 6 


Input

10 9 81


Output

YES
10 1 10 1 10 1 10 1 10 


Input

10 9 82


Output

NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Petya has an array $a$ consisting of $n$ integers. He wants to remove duplicate (equal) elements.

Petya wants to leave only the rightmost entry (occurrence) for each element of the array. The relative order of the remaining unique elements should not be changed.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 50$) — the number of elements in Petya's array.

The following line contains a sequence $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 1\,000$) — the Petya's array.


-----Output-----

In the first line print integer $x$ — the number of elements which will be left in Petya's array after he removed the duplicates.

In the second line print $x$ integers separated with a space — Petya's array after he removed the duplicates. For each unique element only the rightmost entry should be left.


-----Examples-----
Input
6
1 5 5 1 6 1

Output
3
5 6 1 

Input
5
2 4 2 4 4

Output
2
2 4 

Input
5
6 6 6 6 6

Output
1
6 



-----Note-----

In the first example you should remove two integers $1$, which are in the positions $1$ and $4$. Also you should remove the integer $5$, which is in the position $2$.

In the second example you should remove integer $2$, which is in the position $1$, and two integers $4$, which are in the positions $2$ and $4$.

In the third example you should remove four integers $6$, which are in the positions $1$, $2$, $3$ and $4$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Cat Furrier Transform is a popular algorithm among cat programmers to create longcats. As one of the greatest cat programmers ever exist, Neko wants to utilize this algorithm to create the perfect longcat.

Assume that we have a cat with a number x. A perfect longcat is a cat with a number equal 2^m - 1 for some non-negative integer m. For example, the numbers 0, 1, 3, 7, 15 and so on are suitable for the perfect longcats.

In the Cat Furrier Transform, the following operations can be performed on x:

  * (Operation A): you select any non-negative integer n and replace x with x ⊕ (2^n - 1), with ⊕ being a [bitwise XOR operator](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).
  * (Operation B): replace x with x + 1. 



The first applied operation must be of type A, the second of type B, the third of type A again, and so on. Formally, if we number operations from one in the order they are executed, then odd-numbered operations must be of type A and the even-numbered operations must be of type B.

Neko wants to produce perfect longcats at industrial scale, thus for each cat Neko only wants to perform at most 40 operations. Can you help Neko writing a transformation plan?

Note that it is not required to minimize the number of operations. You just need to use no more than 40 operations.

Input

The only line contains a single integer x (1 ≤ x ≤ 10^6).

Output

The first line should contain a single integer t (0 ≤ t ≤ 40) — the number of operations to apply.

Then for each odd-numbered operation print the corresponding number n_i in it. That is, print ⌈ t/2 ⌉ integers n_i (0 ≤ n_i ≤ 30), denoting the replacement x with x ⊕ (2^{n_i} - 1) in the corresponding step.

If there are multiple possible answers, you can print any of them. It is possible to show, that there is at least one answer in the constraints of this problem.

Examples

Input


39


Output


4
5 3 

Input


1


Output


0


Input


7


Output


0

Note

In the first test, one of the transforms might be as follows: 39 → 56 → 57 → 62 → 63. Or more precisely:

  1. Pick n = 5. x is transformed into 39 ⊕ 31, or 56. 
  2. Increase x by 1, changing its value to 57. 
  3. Pick n = 3. x is transformed into 57 ⊕ 7, or 62. 
  4. Increase x by 1, changing its value to 63 = 2^6 - 1. 



In the second and third test, the number already satisfies the goal requirement.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Shashank loves trees and math. He has a rooted tree, $\mathbf{T}$, consisting of $N$ nodes uniquely labeled with integers in the inclusive range $[1,N]$. The node labeled as $1$ is the root node of tree $\mathbf{T}$, and each node in $\mathbf{T}$ is associated with some positive integer value (all values are initially $\mbox{0}$). 

Let's define $\mathbf{F_k}$ as the $k^{th}$ Fibonacci number. Shashank wants to perform $2$ types of operations over his tree, $\mathbf{T}$:

$\mbox{U}$ $\mbox{X}$ $\boldsymbol{\mbox{k}}$

Update the subtree rooted at node $\mbox{X}$ such that the node at level $0$ in subtree $\mbox{X}$ (i.e., node $\mbox{X}$) will have $\mathbf{F_k}$ added to it, all the nodes at level $\mbox{I}$ will have $\boldsymbol{F}_{k+1}$ added to them, and so on. More formally, all the nodes at a distance $\mbox{D}$ from node $\mbox{X}$ in the subtree of node $\mbox{X}$ will have the $(k+D)^{\mathrm{th}}$ Fibonacci number added to them.
$Q$ $\mbox{X}$ $\mathbf{Y}$

Find the sum of all values associated with the nodes on the unique path from $\mbox{X}$ to $\mathbf{Y}$. Print your sum modulo $10^9+7$ on a new line.

Given the configuration for tree $\mathbf{T}$ and a list of $\mbox{M}$ operations, perform all the operations efficiently.

Note: $F_1=F_2=1$.

Input Format

The first line contains $2$ space-separated integers, $N$ (the number of nodes in tree $\mathbf{T}$) and $\mbox{M}$ (the number of operations to be processed), respectively. 

Each line $\boldsymbol{i}$ of the $N-1$ subsequent lines contains an integer, $\mbox{P}$, denoting the parent of the $(i+1)^{th}$ node. 

Each of the $\mbox{M}$ subsequent lines contains one of the two types of operations mentioned in the Problem Statement above.

Constraints

$1\leq N,M\leq10^5$
$1\leq X,Y\leq N$
$1\leq k\leq10^{15}$

Output Format

For each operation of type $2$ (i.e., $Q$), print the required answer modulo $10^9+7$ on a new line.

Sample Input
5 10
1
1
2
2
Q 1 5
U 1 1
Q 1 1
Q 1 2
Q 1 3
Q 1 4
Q 1 5
U 2 2
Q 2 3
Q 4 5

Sample Output
0
1
2
2
4
4
4
10

Explanation

Intially, the tree looks like this:

After update operation $1\:\:1$, it looks like this:

After update operation $\textbf{2}\:\textbf{2}$, it looks like this:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a set $S$ of integers, perform a sequence of the following operations. Note that each value in $S$ must be unique.

* insert($x$): Insert $x$ to $S$ and report the number of elements in $S$ after the operation.
* find($x$): Report the number of $x$ in $S$ (0 or 1).
* delete($x$): Delete $x$ from $S$.
* dump($L$, $R$): Print elements $x$ in $S$ such that $L \leq x \leq R$.

Constraints

* $1 \leq q \leq 200,000$
* $0 \leq x \leq 1,000,000,000$
* The total number of elements printed by dump operations does not exceed $1,000,000$

Input

The input is given in the following format.


$q$
$query_1$
$query_2$
:
$query_q$


Each query $query_i$ is given by


0 $x$


or


1 $x$


or


2 $x$


or


3 $L$ $R$


where the first digits 0, 1, 2 and 3 represent insert, find, delete and dump operations respectively.

Output

For each insert operation, print the number of elements in $S$.
For each find operation, print the number of specified elements in $S$.
For each dump operation, print the corresponding elements in ascending order. Print an element in a line.

Example

Input

9
0 1
0 2
0 3
2 2
1 1
1 2
1 3
0 4
3 2 4


Output

1
2
3
1
0
1
3
3
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

Example:

Input: "Hello World"
Output: 5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K.
(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)
Return the number of good subarrays of A.
 
Example 1:
Input: A = [1,2,1,2,3], K = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

Example 2:
Input: A = [1,2,1,3,4], K = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

 
Note:

1 <= A.length <= 20000
1 <= A[i] <= A.length
1 <= K <= A.length

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a program to obtain a number $(N)$ from the user and display whether the number is a one digit number, 2 digit number, 3 digit number or more than 3 digit number

-----Input:-----
- First line will contain the number $N$,

-----Output:-----
Print "1" if N is a 1 digit number.
Print "2" if N is a 2 digit number.
Print "3" if N is a 3 digit number.
Print "More than 3 digits" if N has more than 3 digits.

-----Constraints-----
- $0 \leq N \leq 1000000$

-----Sample Input:-----
9

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

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Unfortunately, Vasya can only sum pairs of integers (*a*, *b*), such that for any decimal place at least one number has digit 0 in this place. For example, Vasya can sum numbers 505 and 50, but he cannot sum 1 and 4.

Vasya has a set of *k* distinct non-negative integers *d*1,<=*d*2,<=...,<=*d**k*.

Vasya wants to choose some integers from this set so that he could sum any two chosen numbers. What maximal number of integers can he choose in the required manner?

Input Specification:
The first input line contains integer *k* (1<=≤<=*k*<=≤<=100) — the number of integers.

The second line contains *k* distinct space-separated integers *d*1,<=*d*2,<=...,<=*d**k* (0<=≤<=*d**i*<=≤<=100).

Output Specification:
In the first line print a single integer *n* the maximum number of the chosen integers. In the second line print *n* distinct non-negative integers — the required integers.

If there are multiple solutions, print any of them. You can print the numbers in any order.

Demo Input:
['4\n100 10 1 0\n', '3\n2 70 3\n']

Demo Output:
['4\n0 1 10 100 ', '2\n2 70 ']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Harry and Ron are late for their first ever class at Hogwarts.
It is the tranfiguration class. Professor McGonagall is furious
at both of them for being late. She now asks them to perform a
transfiguration spell successfully if they want to attend the class.
The spell involves long palindromic numbers. 

Palindromes are the numbers that reads the same backward as forward. The spell must be able to reduce a palindromic number to another palindrome which will satisfy the following properties :

1.The new palindrome on multiplying with some number should give
back the original palindrome.

2.The length of the old and new palindrome must be same.

Since Harry and Ron have not studied any Transfiguration spell
before the class, they turn to you for help. Program the
spell that will help them out.

Constraints

1 ≤ T ≤ 10000

1 ≤ Length of Palindrome ≤ 10000

Neither the input nor the output shall have leading zeroes

Input

First line contains T no. of test cases.
The next T lines contain a palindromic number each.

Output

Output the new palindrome of each testcase in a new line.

Problem Setter: Vinay Kumar

UPDATE
The output should not be transfigurable any furthur

SAMPLE INPUT
2
6666
6336

SAMPLE OUTPUT
1111
2112

Explanation

For the first test case, 11116=6666. Also no of digits(6666)==no of digits(1111), therefore 1111 is the answer.
For the second test case, 21123=6336. Also no of digits(2112)== no of digits(6336), therefore 2112 is the answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Laurel and Hardy have $n$ piles of chocolates with each pile containing some number of chocolates. The piles are arranged from left to right in a non decreasing order based on the number of chocolates in each pile. They play the following game. 

For every continuous subsequence of chocolate piles (at least 2 piles form a subsequence), Laurel and Hardy will play game on this subsequence of chocolate piles, Laurel plays first, and they play in turn. In one move, the player can choose one of the piles and remove at least one chocolate from it, but the non-decreasing order of the chocolate piles must be maintained. The last person to make a valid move wins. 

How many continuous subsequences of chocolate piles will Laurel win if both of them play optimally? The number of chocolates of each pile will be recovered after the game ends for each subsequences. 

Input Format

The first line contains an integer $n$ denoting the number of piles. 

The second line contains the number of chocolates in each pile, arranged from left to right and separated by a single space between them. 

Constraints

$2$ ≤ $n$ ≤ $\textbf{100000}$ 

$\mbox{I}$ ≤ $chocolates$ $\mbox{in}$ $\textit{each}$ $\textbf{pile}$ ≤ $\mathbf{10^{9}}$

Output Format

A single integer denoting the number of continuous subsequences of chocolate piles in which Laurel will win.

Sample Input
5
1 1 2 2 3

Sample Output
5

Explanation

Of the 10 continuous-sub-sequence of chocolate piles, 

Laurel loses in [1,1], [1,1,2], [1,1,2,2], [1,2,2,3], [2,2] and 

wins in [1,1,2,2,3], [1,2], [1,2,2], [2,2,3] and [2,3] and hence 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp has interviewed Oleg and has written the interview down without punctuation marks and spaces to save time. Thus, the interview is now a string s consisting of n lowercase English letters.

There is a filler word ogo in Oleg's speech. All words that can be obtained from ogo by adding go several times to the end of it are also considered to be fillers. For example, the words ogo, ogogo, ogogogo are fillers, but the words go, og, ogog, ogogog and oggo are not fillers.

The fillers have maximal size, for example, for ogogoo speech we can't consider ogo a filler and goo as a normal phrase. We should consider ogogo as a filler here.

To print the interview, Polycarp has to replace each of the fillers with three asterisks. Note that a filler word is replaced with exactly three asterisks regardless of its length.

Polycarp has dealt with this problem in no time. Can you do the same? The clock is ticking!

Input

The first line contains a positive integer n (1 ≤ n ≤ 100) — the length of the interview.

The second line contains the string s of length n, consisting of lowercase English letters.

Output

Print the interview text after the replacement of each of the fillers with "***". It is allowed for the substring "***" to have several consecutive occurences.

Examples

Input

7
aogogob


Output

a***b


Input

13
ogogmgogogogo


Output

***gmg***


Input

9
ogoogoogo


Output

*********

Note

The first sample contains one filler word ogogo, so the interview for printing is "a***b".

The second sample contains two fillers ogo and ogogogo. Thus, the interview is transformed to "***gmg***".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Many years ago, Roman numbers were defined by only `4` digits: `I, V, X, L`, which represented `1, 5, 10, 50`. These were the only digits used. The value of a sequence was simply the sum of digits in it. For instance:
```
IV = VI = 6
IX = XI = 11
XXL = LXX = XLX = 70
```
It is easy to see that this system is ambiguous, and some numbers could be written in many different ways. Your goal is to determine how many distinct integers could be represented by exactly `n` Roman digits grouped together. For instance:
```Perl
solve(1) = 4, because groups of 1 are [I, V, X, L]. 
solve(2) = 10, because the groups of 2 are [II, VI, VV, XI, XV, XX, IL, VL, XL, LL] corresponding to [2,6,10,11,15,20,51,55,60,100]. 
solve(3) = 20, because groups of 3 start with [III, IIV, IVV, ...etc]
```

`n <= 10E7`

More examples in test cases. Good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A median of an array of integers of length $n$ is the number standing on the $\lceil {\frac{n}{2}} \rceil$ (rounding up) position in the non-decreasing ordering of its elements. Positions are numbered starting with $1$. For example, a median of the array $[2, 6, 4, 1, 3, 5]$ is equal to $3$. There exist some other definitions of the median, but in this problem, we will use the described one.

Given two integers $n$ and $k$ and non-decreasing array of $nk$ integers. Divide all numbers into $k$ arrays of size $n$, such that each number belongs to exactly one array.

You want the sum of medians of all $k$ arrays to be the maximum possible. Find this maximum possible sum.


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases. The next $2t$ lines contain descriptions of test cases.

The first line of the description of each test case contains two integers $n$, $k$ ($1 \leq n, k \leq 1000$).

The second line of the description of each test case contains $nk$ integers $a_1, a_2, \ldots, a_{nk}$ ($0 \leq a_i \leq 10^9$) — given array. It is guaranteed that the array is non-decreasing: $a_1 \leq a_2 \leq \ldots \leq a_{nk}$.

It is guaranteed that the sum of $nk$ for all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case print a single integer — the maximum possible sum of medians of all $k$ arrays.


-----Examples-----

Input
6
2 4
0 24 34 58 62 64 69 78
2 2
27 61 81 91
4 3
2 4 16 18 21 27 36 53 82 91 92 95
3 4
3 11 12 22 33 35 38 67 69 71 94 99
2 1
11 41
3 3
1 1 1 1 1 1 1 1 1
Output
165
108
145
234
11
3


-----Note-----

The examples of possible divisions into arrays for all test cases of the first test:

Test case $1$: $[0, 24], [34, 58], [62, 64], [69, 78]$. The medians are $0, 34, 62, 69$. Their sum is $165$.

Test case $2$: $[27, 61], [81, 91]$. The medians are $27, 81$. Their sum is $108$.

Test case $3$: $[2, 91, 92, 95], [4, 36, 53, 82], [16, 18, 21, 27]$. The medians are $91, 36, 18$. Their sum is $145$.

Test case $4$: $[3, 33, 35], [11, 94, 99], [12, 38, 67], [22, 69, 71]$. The medians are $33, 94, 38, 69$. Their sum is $234$.

Test case $5$: $[11, 41]$. The median is $11$. The sum of the only median is $11$.

Test case $6$: $[1, 1, 1], [1, 1, 1], [1, 1, 1]$. The medians are $1, 1, 1$. Their sum is $3$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once. 


Example 1:

Input: [1,1,2,3,3,4,4,8,8]
Output: 2



Example 2:

Input: [3,3,7,7,10,11,11]
Output: 10



Note:
Your solution should run in O(log n) time and O(1) space.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We often go to supermarkets to buy some fruits or vegetables, and on the tag there prints the price for a kilo. But in some supermarkets, when asked how much the items are, the clerk will say that a yuan for b kilos (You don't need to care about what "yuan" is), the same as a/b yuan for a kilo.

Now imagine you'd like to buy m kilos of apples. You've asked n supermarkets and got the prices. Find the minimum cost for those apples.

You can assume that there are enough apples in all supermarkets.

Input

The first line contains two positive integers n and m (1 ≤ n ≤ 5 000, 1 ≤ m ≤ 100), denoting that there are n supermarkets and you want to buy m kilos of apples.

The following n lines describe the information of the supermarkets. Each line contains two positive integers a, b (1 ≤ a, b ≤ 100), denoting that in this supermarket, you are supposed to pay a yuan for b kilos of apples.

Output

The only line, denoting the minimum cost for m kilos of apples. Please make sure that the absolute or relative error between your answer and the correct answer won't exceed 10^{-6}.

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

Examples

Input

3 5
1 2
3 4
1 3


Output

1.66666667


Input

2 1
99 100
98 99


Output

0.98989899

Note

In the first sample, you are supposed to buy 5 kilos of apples in supermarket 3. The cost is 5/3 yuan.

In the second sample, you are supposed to buy 1 kilo of apples in supermarket 2. The cost is 98/99 yuan.

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