vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Mr. Kitayuta has kindly given you a string s consisting of lowercase English letters. You are asked to insert exactly n lowercase English letters into s to make it a palindrome. (A palindrome is a string that reads the same forward and backward. For example, "noon", "testset" and "a" are all palindromes, while "test" and "kitayuta" are not.) You can choose any n lowercase English letters, and insert each of them to any position of s, possibly to the beginning or the end of s. You have to insert exactly n letters even if it is possible to turn s into a palindrome by inserting less than n letters.

Find the number of the palindromes that can be obtained in this way, modulo 10007.

Input

The first line contains a string s (1 ≤ |s| ≤ 200). Each character in s is a lowercase English letter.

The second line contains an integer n (1 ≤ n ≤ 109).

Output

Print the number of the palindromes that can be obtained, modulo 10007.

Examples

Input

revive
1


Output

1


Input

add
2


Output

28

Note

For the first sample, you can obtain the palindrome "reviver" by inserting 'r' to the end of "revive".

For the second sample, the following 28 palindromes can be obtained: "adada", "adbda", ..., "adzda", "dadad" and "ddadd".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your classmates asked you to copy some paperwork for them. You know that there are 'n' classmates and the paperwork has 'm' pages.

Your task is to calculate how many blank pages do you need.

### Example:
```python
paperwork(5, 5) == 25
```

**Note:** if `n < 0` or `m < 0` return `0`!

Waiting for translations and Feedback! Thanks!

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
On her way to programming school tiger Dasha faced her first test — a huge staircase!

The steps were numbered from one to infinity. As we know, tigers are very fond of all striped things, it is possible that it has something to do with their color. So on some interval of her way she calculated two values — the number of steps with even and odd numbers. 

You need to check whether there is an interval of steps from the *l*-th to the *r*-th (1<=≤<=*l*<=≤<=*r*), for which values that Dasha has found are correct.

Input Specification:
In the only line you are given two integers *a*, *b* (0<=≤<=*a*,<=*b*<=≤<=100) — the number of even and odd steps, accordingly.

Output Specification:
In the only line print "YES", if the interval of steps described above exists, and "NO" otherwise.

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

Demo Output:
['YES\n', 'NO\n']

Note:
In the first example one of suitable intervals is from 1 to 5. The interval contains two even steps — 2 and 4, and three odd: 1, 3 and 5.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
If an integer *a* is divisible by another integer *b*, then *b* is called the divisor of *a*.

For example: 12 has positive 6 divisors. They are 1, 2, 3, 4, 6 and 12.

Let’s define a function *D*(*n*) — number of integers between 1 and *n* (inclusive) which has exactly four positive divisors.

Between 1 and 10 only the integers 6, 8 and 10 has exactly four positive divisors. So, *D*(10)<==<=3.

You are given an integer *n*. You have to calculate *D*(*n*).

Input Specification:
The only line contains integer *n* (1<=≤<=*n*<=≤<=1011) — the parameter from the problem statement.

Output Specification:
Print the only integer *c* — the number of integers between 1 and *n* with exactly four divisors.

Demo Input:
['10\n', '20\n']

Demo Output:
['3\n', '5\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given K eggs, and you have access to a building with N floors from 1 to N. 
Each egg is identical in function, and if an egg breaks, you cannot drop it again.
You know that there exists a floor F with 0 <= F <= N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break.
Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N). 
Your goal is to know with certainty what the value of F is.
What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F?
 



Example 1:
Input: K = 1, N = 2
Output: 2
Explanation: 
Drop the egg from floor 1.  If it breaks, we know with certainty that F = 0.
Otherwise, drop the egg from floor 2.  If it breaks, we know with certainty that F = 1.
If it didn't break, then we know with certainty F = 2.
Hence, we needed 2 moves in the worst case to know what F is with certainty.


Example 2:
Input: K = 2, N = 6
Output: 3


Example 3:
Input: K = 3, N = 14
Output: 4

 
Note:

1 <= K <= 100
1 <= N <= 10000

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

Real variables $ x_1, x_2, ..., x_N $ satisfy the following conditions.

1. $ 0 \ leq x_i \ leq 1 $ ($ 1 \ leq i \ leq N $)
2. $ w_1x_1 + w_2x_2 + ... + w_Nx_N \ leq W $



At this time, find the maximum value that $ v_1x_1 + v_2x_2 + ... + v_Nx_N $ can take. It is known that such a maximum actually exists.

Constraint

* $ 1 \ leq N \ leq 10 ^ 5 $
* $ 1 \ leq W \ leq 10 ^ 5 $
* $ -10 ^ 4 \ leq w_i \ leq 10 ^ 4 $
* $ -10 ^ 4 \ leq v_i \ leq 10 ^ 4 $



input

Input follows the following format. All given numbers are integers.


$ N $ $ W $
$ w_1 $ $ v_1 $
$ w_2 $ $ v_2 $
$ ... $
$ w_N $ $ v_N $

output

Output the maximum possible value of $ v_1x_1 + v_2x_2 + ... + v_Nx_N $ on one line. The output must not have an error greater than $ 10 ^ {-3} $.

Examples

Input

1 1
3 1


Output

0.333333


Input

2 3
3 3
1 2


Output

4.000000


Input

2 1
-1 -3
3 10


Output

3.666667

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two kids are playing the following game: there are initially N cards and there is a non-negative integer written on the each card. They perform three steps:
The first player picks random card of the given N cards. Let's denote the number written on it as A. 
The second player picks random card of the other N - 1 cards. Let's  denote the number written on it as B.
If A equals B then, the game ends with a draw and nobody receives candies. Otherwise the game is finished. The kid with the greatest number is claimed as the winner and he gets |B - A| sweets.

You were watching your little son playing this game and noticed that there are not many outcomes  of the game. So now you are interested in the following question: how many different values of |A-B| are possible?

Input
The first line contains one integer N.
The second line contains N non-negative integers - numbers written on cards.

Output
Output the one number - answer to the question.

Constraints
2 ≤ N ≤ 10^5
0 ≤ A[i] ≤ 10^5

SAMPLE INPUT
3
4 8 6

SAMPLE OUTPUT
2

Explanation

The winner can get 2 sweets if the chosen cards were 6 and 8 (or 4 and 6). He also can get 4 sweets if the numbers on the cards were 4 and 8.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Summation Of Primes

The sum of the primes below or equal to 10 is **2 + 3 + 5 + 7 = 17**. Find the sum of all the primes **_below or equal to the number passed in_**.

From Project Euler's [Problem #10](https://projecteuler.net/problem=10 "Project Euler - Problem 10").

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As you might already know, space has always been a problem in ICPC Jakarta. To cope with this, ICPC Jakarta is planning to build two new buildings. These buildings should have a shape of a rectangle of the same size. Now, their problem is to find land to build the buildings.

There are N lands available for sale. The i^{th} land has a rectangular shape of size L_i × W_i. For a good feng shui, the building's side should be parallel to the land's sides.

One way is to build the two buildings on two different lands, one on each land (not necessarily with the same orientation). A building of size A × B can be build on the i^{th} land if and only if at least one of the following is satisfied: 

  * A ≤ L_i and B ≤ W_i, or 
  * A ≤ W_i and B ≤ L_i. 

Alternatively, it is also possible to build two buildings of A × B on the i^{th} land with the same orientation. Formally, it is possible to build two buildings of A × B on the i^{th} land if and only if at least one of the following is satisfied: 
  * A × 2 ≤ L_i and B ≤ W_i, or 
  * A × 2 ≤ W_i and B ≤ L_i, or 
  * A ≤ L_i and B × 2 ≤ W_i, or 
  * A ≤ W_i and B × 2 ≤ L_i. 



Your task in this problem is to help ICPC Jakarta to figure out the largest possible buildings they can build given N available lands. Note that ICPC Jakarta has to build two buildings of A × B; output the largest possible for A × B.

Input

Input begins with a line containing an integer: N (1 ≤ N ≤ 100 000) representing the number of available lands. The next N lines each contains two integers: L_i W_i (1 ≤ L_i, W_i ≤ 10^9) representing the size of the land.

Output

Output in a line a number representing the largest building that ICPC Jakarta can build with exactly one decimal point (see sample input/output for clarity).

Examples

Input


2
5 5
3 4


Output


12.5


Input


2
2 5
4 3


Output


8.0


Input


3
10 1
9 8
7 6


Output


42.0

Note

Explanation for the sample input/output #1

Two buildings of 2.5 × 5 can be built both on the first land.

Explanation for the sample input/output #2

Two buildings of 2 × 4 can be built each on the first and second lands.

Explanation for the sample input/output #3

Two buildings of 7 × 6 can be built each on the second and third lands.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have an array of unique elements. A special kind of permutation is the one that has all of its elements in a different position than the original.

Let's see how many of these permutations may be generated from an array of four elements. We put the original array with square brackets and the wanted permutations with parentheses. 
```
arr = [1, 2, 3, 4]
      (2, 1, 4, 3)
      (2, 3, 4, 1)
      (2, 4, 1, 3)
      (3, 1, 4, 2)
      (3, 4, 1, 2)
      (3, 4, 2, 1)
      (4, 1, 2, 3)
      (4, 3, 1, 2)
      (4, 3, 2, 1)
      _____________
A total of 9 permutations with all their elements in different positions than arr
```

The task for this kata would be to create a code to count all these permutations for an array of certain length.

Features of the random tests:
```
l = length of the array
10 ≤ l ≤ 5000
```

See the example tests.

Enjoy it!

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a description of a depot. It is a rectangular checkered field of *n*<=×<=*m* size. Each cell in a field can be empty (".") or it can be occupied by a wall ("*"). 

You have one bomb. If you lay the bomb at the cell (*x*,<=*y*), then after triggering it will wipe out all walls in the row *x* and all walls in the column *y*.

You are to determine if it is possible to wipe out all walls in the depot by placing and triggering exactly one bomb. The bomb can be laid both in an empty cell or in a cell occupied by a wall.

Input Specification:
The first line contains two positive integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=1000) — the number of rows and columns in the depot field. 

The next *n* lines contain *m* symbols "." and "*" each — the description of the field. *j*-th symbol in *i*-th of them stands for cell (*i*,<=*j*). If the symbol is equal to ".", then the corresponding cell is empty, otherwise it equals "*" and the corresponding cell is occupied by a wall.

Output Specification:
If it is impossible to wipe out all walls by placing and triggering exactly one bomb, then print "NO" in the first line (without quotes).

Otherwise print "YES" (without quotes) in the first line and two integers in the second line — the coordinates of the cell at which the bomb should be laid. If there are multiple answers, print any of them.

Demo Input:
['3 4\n.*..\n....\n.*..\n', '3 3\n..*\n.*.\n*..\n', '6 5\n..*..\n..*..\n*****\n..*..\n..*..\n..*..\n']

Demo Output:
['YES\n1 2\n', 'NO\n', 'YES\n3 3\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya has an array a_1, a_2, ..., a_n.

You don't know this array, but he told you m facts about this array. The i-th fact is a triple of numbers t_i, l_i and r_i (0 ≤ t_i ≤ 1, 1 ≤ l_i < r_i ≤ n) and it means:

  * if t_i=1 then subbarray a_{l_i}, a_{l_i + 1}, ..., a_{r_i} is sorted in non-decreasing order; 
  * if t_i=0 then subbarray a_{l_i}, a_{l_i + 1}, ..., a_{r_i} is not sorted in non-decreasing order. A subarray is not sorted if there is at least one pair of consecutive elements in this subarray such that the former is greater than the latter. 



For example if a = [2, 1, 1, 3, 2] then he could give you three facts: t_1=1, l_1=2, r_1=4 (the subarray [a_2, a_3, a_4] = [1, 1, 3] is sorted), t_2=0, l_2=4, r_2=5 (the subarray [a_4, a_5] = [3, 2] is not sorted), and t_3=0, l_3=3, r_3=5 (the subarray [a_3, a_5] = [1, 3, 2] is not sorted).

You don't know the array a. Find any array which satisfies all the given facts.

Input

The first line contains two integers n and m (2 ≤ n ≤ 1000, 1 ≤ m ≤ 1000).

Each of the next m lines contains three integers t_i, l_i and r_i (0 ≤ t_i ≤ 1, 1 ≤ l_i < r_i ≤ n).

If t_i = 1 then subbarray a_{l_i}, a_{l_i + 1}, ... , a_{r_i} is sorted. Otherwise (if t_i = 0) subbarray a_{l_i}, a_{l_i + 1}, ... , a_{r_i} is not sorted.

Output

If there is no array that satisfies these facts in only line print NO (in any letter case).

If there is a solution, print YES (in any letter case). In second line print n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9) — the array a, satisfying all the given facts. If there are multiple satisfying arrays you can print any of them.

Examples

Input


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


Output


YES
1 2 2 3 5 4 4


Input


4 2
1 1 4
0 2 3


Output


NO

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

Given a binary string $S$ consisting of $0's$ and $1's$, find whether there exists a rightwise  [circular rotation] of the string such that every 2 adjacent $1's$ are separated by at most $C$ $0's$.

Note: The last occurrence of $1$ in the rotated string won't have any $1$ next to it, i.e, first and the last ones in the string are not considered to be adjacent.

------ Input: ------

First line will contain $T$, number of testcases. Then the testcases follow. 
Each testcase contains of two lines of input.
First line contains two space separated integers $N, C$, length of the string and the upper limit on a number of $0's$ between $2$ adjacent $1's$.
Second line contains the binary string $S$.

------ Output: ------
For each testcase, output in a single line "YES" if there exists a rightwise circular rotation of string satisfying the criteria and "NO" if it doesn't exist.

Note: The output is case-insensitive ― each letter may be printed in upper case or lower case.

------ Constraints  ------
$1 ≤ N ≤ 5*10^{5}$
$0 ≤ C ≤ max(0, N - 2)$
Sum of $N$ over all tests is atmost $10^{6}$.

----- Sample Input 1 ------ 
3

4 1

1100

4 0

0101

6 1

101001
----- Sample Output 1 ------ 
YES

NO

YES
----- explanation 1 ------ 
Case 1: In the original configuration maximum number of $0's$ between $2$ adjacent $1's$ is $0$, therefore it satisfies the criteria.

Case 2: The $4$ circular rotations of the string S = {"0101", "1010", "0101", "1010"}. In all the cases the maximum number of $0's$ between $2$ consecutive $1's$ is $1$ which doesn't satisfies the criteria.

Case 3: The $6$ circular rotations of the string S = {"101001", "110100", "011010", "001101", "100110", "010011"} out of which $second$, $third$ and $fourth$ strings satisfy the criteria.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

Example 1:


Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2

For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.

00 - 0
10 - 2
11 - 3
01 - 1


Example 2:


Input: 0
Output: [0]
Explanation: We define the gray code sequence to begin with 0.
             A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1.
             Therefore, for n = 0 the gray code sequence is [0].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a hotel with the following accommodation fee:

* X yen (the currency of Japan) per night, for the first K nights
* Y yen per night, for the (K+1)-th and subsequent nights



Tak is staying at this hotel for N consecutive nights. Find his total accommodation fee.

Constraints

* 1 \leq N, K \leq 10000
* 1 \leq Y < X \leq 10000
* N,\,K,\,X,\,Y are integers.

Input

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


N
K
X
Y


Output

Print Tak's total accommodation fee.

Examples

Input

5
3
10000
9000


Output

48000


Input

2
3
10000
9000


Output

20000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Planning The Expedition

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Natasha is planning an expedition to Mars for $n$ people. One of the important tasks is to provide food for each participant.

The warehouse has $m$ daily food packages. Each package has some food type $a_i$.

Each participant must eat exactly one food package each day. Due to extreme loads, each participant must eat the same food type throughout the expedition. Different participants may eat different (or the same) types of food.

Formally, for each participant $j$ Natasha should select his food type $b_j$ and each day $j$-th participant will eat one food package of type $b_j$. The values $b_j$ for different participants may be different.

What is the maximum possible number of days the expedition can last, following the requirements above?

Input Specification:
The first line contains two integers $n$ and $m$ ($1 \le n \le 100$, $1 \le m \le 100$) — the number of the expedition participants and the number of the daily food packages available.

The second line contains sequence of integers $a_1, a_2, \dots, a_m$ ($1 \le a_i \le 100$), where $a_i$ is the type of $i$-th food package.

Output Specification:
Print the single integer — the number of days the expedition can last. If it is not possible to plan the expedition for even one day, print 0.

Demo Input:
['4 10\n1 5 2 1 1 1 2 5 7 2\n', '100 1\n1\n', '2 5\n5 4 3 2 1\n', '3 9\n42 42 42 42 42 42 42 42 42\n']

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

Note:
In the first example, Natasha can assign type $1$ food to the first participant, the same type $1$ to the second, type $5$ to the third and type $2$ to the fourth. In this case, the expedition can last for $2$ days, since each participant can get two food packages of his food type (there will be used $4$ packages of type $1$, two packages of type $2$ and two packages of type $5$).

In the second example, there are $100$ participants and only $1$ food package. In this case, the expedition can't last even $1$ day.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's denote a $k$-step ladder as the following structure: exactly $k + 2$ wooden planks, of which

  two planks of length at least $k+1$ — the base of the ladder;  $k$ planks of length at least $1$ — the steps of the ladder; 

Note that neither the base planks, nor the steps planks are required to be equal.

For example, ladders $1$ and $3$ are correct $2$-step ladders and ladder $2$ is a correct $1$-step ladder. On the first picture the lengths of planks are $[3, 3]$ for the base and $[1]$ for the step. On the second picture lengths are $[3, 3]$ for the base and $[2]$ for the step. On the third picture lengths are $[3, 4]$ for the base and $[2, 3]$ for the steps. 

 $H - 1 =$ 

You have $n$ planks. The length of the $i$-th planks is $a_i$. You don't have a saw, so you can't cut the planks you have. Though you have a hammer and nails, so you can assemble the improvised "ladder" from the planks.

The question is: what is the maximum number $k$ such that you can choose some subset of the given planks and assemble a $k$-step ladder using them?


-----Input-----

The first line contains a single integer $T$ ($1 \le T \le 100$) — the number of queries. The queries are independent.

Each query consists of two lines. The first line contains a single integer $n$ ($2 \le n \le 10^5$) — the number of planks you have.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$) — the lengths of the corresponding planks.

It's guaranteed that the total number of planks from all queries doesn't exceed $10^5$.


-----Output-----

Print $T$ integers — one per query. The $i$-th integer is the maximum number $k$, such that you can choose some subset of the planks given in the $i$-th query and assemble a $k$-step ladder using them.

Print $0$ if you can't make even $1$-step ladder from the given set of planks.


-----Example-----
Input
4
4
1 3 1 3
3
3 3 2
5
2 3 3 4 2
3
1 1 2

Output
2
1
2
0



-----Note-----

Examples for the queries $1-3$ are shown at the image in the legend section.

The Russian meme to express the quality of the ladders:

 [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You’d like to figure out whether a car was speeding while it was driving down a straight road. Unfortunately, you don’t have any radar guns or related instruments for measuring speed directly; all you have are photographs taken of the car at various checkpoints on the road at various times. Given when and where these photographs were taken, what is the fastest speed that you can prove the car must have been going at some point along the road?

-----Input-----
The first line of input contains an integer $n$ ($2 \le n \le 100$), which is the number of photographs taken.

Each of the following $n$ lines contains two space-separated integers $t$ ($0 \le t \le 10^4$) and

$d$ ($0 \le d \le 10^6$), where $t$ is the time of the photograph in hours, and $d$ is the distance along the road in miles. The first photograph is always taken at time $0$ with distance $0$, and both the times and distances strictly increase.

-----Output-----
Output a single integer, which is the greatest integral speed that you can be certain the car was going at some point in miles per hour.

-----Examples-----
Sample Input:
2
0 0
7 42
Sample Output:
6

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