vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
There are 2N points evenly spaced on the circumference of a circle. These points are numbered 1 to 2N in clockwise order, starting from some of them.

Snuke will divide these points into N pairs, then for each pair, he will draw a line segment connecting the two points. After the line segments are drawn, two points are connected when one can reach from one of those points to the other by traveling only on the line segments. The number of the connected parts here is the number of the connected components in the graph with 2N vertices, corresponding to the 2N points, where every pair of vertices corresponding to two connected points is connected with an edge.

Snuke has already decided K of the pairs, and the i-th of them is a pair of Point A_i and Point B_i.

He is thinking of trying all possible ways to make the remaining N-K pairs and counting the number of the connected parts for each of those ways. Find the sum of those numbers of the connected parts. As the answer can be extremely large, compute the sum modulo 10^9+7.

Constraints

* 1 \leq N \leq 300
* 0 \leq K \leq N
* 1 \leq A_i,B_i \leq 2N
* A_1,\ A_2,\ ...\ A_K,\ B_1,\ B_2,\ ...\ B_K are all distinct.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N K
A_1 B_1
A_2 B_2
:
A_K B_K


Output

Print the sum of the numbers of the connected parts for all possible ways to make the remaining N-K pairs.

Examples

Input

2 0


Output

5


Input

4 2
5 2
6 1


Output

6


Input

20 10
10 18
11 17
14 7
4 6
30 28
19 24
29 22
25 32
38 34
36 39


Output

27087418

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For given a sequence $A = \\{a_0, a_1, ..., a_{n-1}\\}$, print the previous permutation and the next permutation in lexicographic order.

Constraints

* $1 \leq n \leq 9$
* $a_i$ consist of $1, 2, ..., n$

Input

A sequence is given in the following format.


$n$
$a_0 \; a_1 \; ... \; a_{n-1}$


Output

Print the previous permutation, the given sequence and the next permutation in the 1st, 2nd and 3rd lines respectively. Separate adjacency elements by a space character. Note that if there is no permutation, print nothing in the corresponding line.

Examples

Input

3
2 1 3


Output

1 3 2
2 1 3
2 3 1


Input

3
3 2 1


Output

3 1 2
3 2 1

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Once again Tavas started eating coffee mix without water! Keione told him that it smells awful, but he didn't stop doing that. That's why Keione told his smart friend, SaDDas to punish him! SaDDas took Tavas' headphones and told him: "If you solve the following problem, I'll return it to you."

The problem is: 

You are given a lucky number *n*. Lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

If we sort all lucky numbers in increasing order, what's the 1-based index of *n*? 

Tavas is not as smart as SaDDas, so he asked you to do him a favor and solve this problem so he can have his headphones back.

Input Specification:
The first and only line of input contains a lucky number *n* (1<=≤<=*n*<=≤<=109).

Output Specification:
Print the index of *n* among all lucky numbers.

Demo Input:
['4\n', '7\n', '77\n']

Demo Output:
['1\n', '2\n', '6\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
At Moscow Workshops ICPC team gets a balloon for each problem they solved first. Team MSU Red Panda got so many balloons that they didn't know how to spend them. So they came up with a problem with them.

There are several balloons, not more than 10^6 in total, each one is colored in one of k colors. We can perform the following operation: choose k-1 balloons such that they are of k-1 different colors, and recolor them all into remaining color. We can perform this operation any finite number of times (for example, we can only perform the operation if there are at least k-1 different colors among current balls).

How many different balloon configurations can we get? Only number of balloons of each color matters, configurations differing only by the order of balloons are counted as equal. As this number can be very large, output it modulo 998244353.

Input

The first line contains a single integer k (2 ≤ k ≤ 10^5) —the number of colors.

The second line contains k integers a_1, a_2, …, a_k (0 ≤ a_i) —initial configuration of balloons. a_i is number of balloons of color i. The total number of balloons doesn't exceed 10^6. In other words,

a_1 + a_2 + a_3 + … + a_k ≤ 10^6.

Output

Output number of possible configurations modulo 998244353.

Examples

Input


3
0 1 2


Output


3


Input


4
1 1 1 1


Output


5

Input


5
0 0 1 2 3


Output


1

Input


3
2 2 8


Output


31

Note

In the first example, there are 3 configurations we can get: [0, 1, 2], [2, 0, 1], [1, 2, 0].

In the second example, we can apply the operation not more than once, and possible configurations are: [1, 1, 1, 1], [0, 0, 0, 4], [0, 0, 4, 0], [0, 4, 0, 0], [4, 0, 0, 0]. 

In the third example, we can't apply any operations, so the only achievable configuration is the starting one.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Zane and Zane's crush have just decided to date! However, the girl is having a problem with her Physics final exam, and needs your help.

There are n questions, numbered from 1 to n. Question i comes before question i + 1 (1 ≤ i < n). Each of the questions cannot be guessed on, due to the huge penalty for wrong answers. The girl luckily sits in the middle of two geniuses, so she is going to cheat.

<image>

However, the geniuses have limitations. Each of them may or may not know the answers to some questions. Anyway, it is safe to assume that the answers on their answer sheets are absolutely correct.

To make sure she will not get caught by the proctor, the girl will glance at most p times, each time looking at no more than k consecutive questions on one of the two geniuses' answer sheet. When the girl looks at some question on an answer sheet, she copies the answer to that question if it is on that answer sheet, or does nothing otherwise.

Help the girl find the maximum number of questions she can get correct.

Input

The first line contains three integers n, p, and k (1 ≤ n, p ≤ 1, 000, 1 ≤ k ≤ min(n, 50)) — the number of questions, the maximum number of times the girl can glance, and the maximum number of consecutive questions that can be looked at in one time glancing, respectively.

The second line starts with one integer r (0 ≤ r ≤ n), denoting the number of questions the first genius has answered on his answer sheet. Then follow r integers a1, a2, ..., ar (1 ≤ ai ≤ n) — the answered questions, given in a strictly-increasing order (that is, ai < ai + 1).

The third line starts with one integer s (0 ≤ s ≤ n), denoting the number of questions the second genius has answered on his answer sheet. Then follow s integers b1, b2, ..., bs (1 ≤ bi ≤ n) — the answered questions, given in a strictly-increasing order (that is, bi < bi + 1).

Output

Print one integer — the maximum number of questions the girl can answer correctly.

Examples

Input

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


Output

4

Input

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


Output

7

Note

Let (x, l, r) denote the action of looking at all questions i such that l ≤ i ≤ r on the answer sheet of the x-th genius.

In the first sample, the girl could get 4 questions correct by performing sequence of actions (1, 1, 3) and (2, 5, 6).

In the second sample, the girl could perform sequence of actions (1, 3, 5), (2, 2, 4), and (2, 6, 8) to get 7 questions correct.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Summer sell-off

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Summer holidays! Someone is going on trips, someone is visiting grandparents, but someone is trying to get a part-time job. This summer Noora decided that she wants to earn some money, and took a job in a shop as an assistant.

Shop, where Noora is working, has a plan on the following *n* days. For each day sales manager knows exactly, that in *i*-th day *k**i* products will be put up for sale and exactly *l**i* clients will come to the shop that day. Also, the manager is sure, that everyone, who comes to the shop, buys exactly one product or, if there aren't any left, leaves the shop without buying anything. Moreover, due to the short shelf-life of the products, manager established the following rule: if some part of the products left on the shelves at the end of the day, that products aren't kept on the next day and are sent to the dump.

For advertising purposes manager offered to start a sell-out in the shop. He asked Noora to choose any *f* days from *n* next for sell-outs. On each of *f* chosen days the number of products were put up for sale would be doubled. Thus, if on *i*-th day shop planned to put up for sale *k**i* products and Noora has chosen this day for sell-out, shelves of the shop would keep 2·*k**i* products. Consequently, there is an opportunity to sell two times more products on days of sell-out.

Noora's task is to choose *f* days to maximize total number of sold products. She asks you to help her with such a difficult problem.

Input Specification:
The first line contains two integers *n* and *f* (1<=≤<=*n*<=≤<=105,<=0<=≤<=*f*<=≤<=*n*) denoting the number of days in shop's plan and the number of days that Noora has to choose for sell-out.

Each line of the following *n* subsequent lines contains two integers *k**i*,<=*l**i* (0<=≤<=*k**i*,<=*l**i*<=≤<=109) denoting the number of products on the shelves of the shop on the *i*-th day and the number of clients that will come to the shop on *i*-th day.

Output Specification:
Print a single integer denoting the maximal number of products that shop can sell.

Demo Input:
['4 2\n2 1\n3 5\n2 3\n1 5\n', '4 1\n0 2\n0 3\n3 5\n0 6\n']

Demo Output:
['10', '5']

Note:
In the first example we can choose days with numbers 2 and 4 for sell-out. In this case new numbers of products for sale would be equal to [2, 6, 2, 2] respectively. So on the first day shop will sell 1 product, on the second — 5, on the third — 2, on the fourth — 2. In total 1 + 5 + 2 + 2 = 10 product units.

In the second example it is possible to sell 5 products, if you choose third day for sell-out.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Valera is a coder. Recently he wrote a funny program. The pseudo code for this program is given below:
    
    
      
    //input: integers x, k, p  
    a = x;  
    for(step = 1; step <= k; step = step + 1){  
        rnd = [random integer from 1 to 100];  
        if(rnd <= p)  
            a = a * 2;  
        else  
            a = a + 1;  
    }  
      
    s = 0;  
      
    while(remainder after dividing a by 2 equals 0){  
        a = a / 2;  
        s = s + 1;  
    }  
      
    

Now Valera wonders: given the values x, k and p, what is the expected value of the resulting number s?

Input

The first line of the input contains three integers x, k, p (1 ≤ x ≤ 109; 1 ≤ k ≤ 200; 0 ≤ p ≤ 100).

Output

Print the required expected value. Your answer will be considered correct if the absolute or relative error doesn't exceed 10 - 6.

Examples

Input

1 1 50


Output

1.0000000000000


Input

5 3 0


Output

3.0000000000000


Input

5 3 25


Output

1.9218750000000

Note

If the concept of expected value is new to you, you can read about it by the link: 

http://en.wikipedia.org/wiki/Expected_value

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

I often buy Coca-Cola from the vending machine at work. Usually, I buy several cokes at once, since my working mates also like coke. A coke in the vending machine costs 8 Rupees, and the machine accepts coins with the values 1, 5 and 10 Rupees only. 

As soon as I press the coke button (After having inserted sufficient amount of money), I receive a coke followed by the exchange (i.e the excess amount, if any). The exchange is always given in as few coins as possible (this is uniquely determined by the coin set used). This procedure is repeated until I've bought all the cokes I want. 

Note that I can pick up the coin exchange and use those coins when buying further cokes. The vending  machine doesn't support buying more than one coke at the same time, if you want to buy more than one, you should pay for the first one, then get the exchange then insert money for the second one and so on.

Now, what is the least number of coins I must insert in total, given the number of cokes I want to buy and the number of coins I have of each value? You may assume that the machine won't run out of coins. If the given number of coins is insufficient to buy the quantity of cokes required, you can output "-1".

Input:
The first line in the input contains the number of test cases. Each case is then given on a line by itself. A test case consists of four integers: C (the number of cokes I want to buy), n1, n5, n10 (the number of coins of value 1, 5 and 10, respectively). 

Output:
For each test case, output a line containing a single integer: the minimum number of coins needed to insert into the vending machine. 

Constraints:
1 ≤ T ≤10
1 ≤ C ≤ 150 
0 ≤ n1 ≤ 500 
0 ≤ n5 ≤ 100 
0 ≤ n10 ≤ 50  

SAMPLE INPUT
3
2 2 1 1
2 1 4 1
3 1 1 1

SAMPLE OUTPUT
5
3
-1

Explanation

Test case 1, 

   For buying the 1st coke: Insert one 10 Rupee coin. The machine gives back two 1 Rupee coins in exchange.

   For buying the 2nd coke: Insert one 5 Rupee coin and three 1 Rupee coins.

Therefore a total of 5 coins were inserted.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A polyomino is a polyform with the square as its base form. It is a connected shape formed as the union of one or more identical squares in distinct locations on the plane, taken from the regular square tiling, such that every square can be connected to every other square through a sequence of shared edges (i.e., shapes connected only through shared corners of squares are not permitted).

 The most well-known polyominos are the seven tetrominos made out of four squares (see figure), famous from the Tetris® game, and of course the single domino consisting of two squares from the game with the same name. Some polyomino can be obtained by gluing several copies of the same smaller polyomino translated (but not rotated or mirrored) to different locations in the plane. We call those polyomino powers.



-----Input-----
One line with two positive integers $h, w \leq 10$. Next follows an $h \times w$ matrix of characters ‘.’ or ‘X’, the ‘X’s describing a polyomino and ‘.’ space.

-----Output-----
A $k$-power with $2 \leq k \leq 5$ copies of a smaller polyomino: Output a $h\times w$ matrix on the same format as the input with the ‘X’s replaced by the numbers $1$ through $k$ in any order identifying the factor pieces. Furthermore, if multiple solutions exist, any will do. Otherwise, output “No solution” if no solution exists.

-----Examples-----
Sample Input 1:
3 7
.XXXXX.
.XX..X.
XXXX...
Sample Output 1:
No solution

Sample Input 2:
1 3
XXX
Sample Output 2:
123

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasya had a strictly increasing sequence of positive integers *a*1, ..., *a**n*. Vasya used it to build a new sequence *b*1, ..., *b**n*, where *b**i* is the sum of digits of *a**i*'s decimal representation. Then sequence *a**i* got lost and all that remained is sequence *b**i*.

Vasya wonders what the numbers *a**i* could be like. Of all the possible options he likes the one sequence with the minimum possible last number *a**n*. Help Vasya restore the initial sequence.

It is guaranteed that such a sequence always exists.

Input Specification:
The first line contains a single integer number *n* (1<=≤<=*n*<=≤<=300).

Next *n* lines contain integer numbers *b*1, ..., *b**n*  — the required sums of digits. All *b**i* belong to the range 1<=≤<=*b**i*<=≤<=300.

Output Specification:
Print *n* integer numbers, one per line — the correct option for numbers *a**i*, in order of following in sequence. The sequence should be strictly increasing. The sum of digits of the *i*-th number should be equal to *b**i*. 

If there are multiple sequences with least possible number *a**n*, print any of them. Print the numbers without leading zeroes.

Demo Input:
['3\n1\n2\n3\n', '3\n3\n2\n1\n']

Demo Output:
['1\n2\n3\n', '3\n11\n100\n']

Note:
none

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

Given two sequences of length $ N $, $ A $ and $ B $. First, the $ i $ item in the sequence $ A $ is $ a_i $, and the $ i $ item in the sequence $ B $ is $ b_i $.

Since a total of $ Q $ of statements of the following format are given, create a program that processes in the given order.

Each statement is represented by three integers $ x, y, z $.

* Set the value of the $ y $ item in the sequence $ A $ to $ z $. (When $ x = 1 $)
* Set the value of the $ y $ item in the sequence $ B $ to $ z $. (When $ x = 2 $)
* Find and report the smallest value in the $ z $ item from the $ y $ item in the sequence $ A $. (When $ x = 3 $)
* Find and report the smallest value in the $ z $ item from the $ y $ item in the sequence $ B $. (When $ x = 4 $)
* Change the sequence $ A $ to be exactly the same as the sequence $ B $. (When $ x = 5 $)
* Change the sequence $ B $ to be exactly the same as the sequence $ A $. (When $ x = 6 $)

Constraints

The input satisfies the following conditions.

* $ 2 \ le N \ le 2 \ times 10 ^ 5 $
* $ 2 \ le Q \ le 2 \ times 10 ^ 5 $
* $ 1 \ le a_i \ le 10 ^ 9 $
* $ 1 \ le b_i \ le 10 ^ 9 $
* $ 1 \ le x_i \ le 6 $
* $ 1 \ le y_i \ le N $ (when $ 1 \ le x_i \ le 4 $)
* $ y_i = -1 $ (when $ x_i = 5, 6 $)
* $ 1 \ le z_i \ le 10 ^ 9 $ (when $ x_i = 1, 2 $)
* $ y_i \ le z_i \ le N $ (when $ x_i = 3, 4 $)
* $ z_i = -1 $ (when $ x_i = 5, 6 $)
* All inputs are integers

Input

The input is given in the following format.

$ N $
$ a_ {1} $ $ a_ {2} $ ... $ a_ {N} $
$ b_ {1} $ $ b_ {2} $ ... $ b_ {N} $
$ Q $
$ x_1 $ $ y_1 $ $ z_1 $
$ x_2 $ $ y_2 $ $ z_2 $
...
$ x_Q $ $ y_Q $ $ z_Q $

Output

Every time a statement of $ x = 3 $ or $ x = 4 $ is given by input, the found value is output on one line.

Example

Input

5
1 3 5 7 9
6 2 3 2 6
10
1 3 4
3 4 5
4 2 3
5 -1 -1
2 3 8
3 2 5
4 3 3
1 1 1
6 -1 -1
3 1 5


Output

7
2
2
8
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Peter got a new snow blower as a New Year present. Of course, Peter decided to try it immediately. After reading the instructions he realized that it does not work like regular snow blowing machines. In order to make it work, you need to tie it to some point that it does not cover, and then switch it on. As a result it will go along a circle around this point and will remove all the snow from its path.

Formally, we assume that Peter's machine is a polygon on a plane. Then, after the machine is switched on, it will make a circle around the point to which Peter tied it (this point lies strictly outside the polygon). That is, each of the points lying within or on the border of the polygon will move along the circular trajectory, with the center of the circle at the point to which Peter tied his machine.

Peter decided to tie his car to point P and now he is wondering what is the area of ​​the region that will be cleared from snow. Help him.

Input

The first line of the input contains three integers — the number of vertices of the polygon n (<image>), and coordinates of point P.

Each of the next n lines contains two integers — coordinates of the vertices of the polygon in the clockwise or counterclockwise order. It is guaranteed that no three consecutive vertices lie on a common straight line.

All the numbers in the input are integers that do not exceed 1 000 000 in their absolute value.

Output

Print a single real value number — the area of the region that will be cleared. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6. 

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if <image>.

Examples

Input

3 0 0
0 1
-1 2
1 2


Output

12.566370614359172464


Input

4 1 -1
0 0
1 2
2 0
1 1


Output

21.991148575128551812

Note

In the first sample snow will be removed from that area:

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider a string A = "12345".  An infinite string is built by performing infinite steps on A recursively. In i^{th} step, A is concatenated with ‘$’ i times followed by reverse of A, that is, A = A | $...$ | reverse(A), where | denotes concatenation.
Given a position pos, find out the character at pos in the infinite string.
Example 1:
Input: pos = 3
Output: 3
Explanation: A = "12345", then A[pos] is 3.
Example 2:
Input: pos = 10
Output: 2
Explanation: A = "12345$54321", then A[pos] is 2.
Your Task:  
You dont need to read input or print anything. Complete the function posInfinite() which takes pos as input parameter and returns the character in the infinite string at pos.
Expected Time Complexity: O(sqrtn)
Expected Auxiliary Space: O(1)
Constraints:
1<= pos <=10^{12}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Theta has been learning about powers of $2$ in school. She notices that some numbers when written out contain powers of $2$ in their digit representation: for instance, $12560$ contains $256$ which is a power of $2$. She has been wondering how many such numbers there are.

Can you write a program that counts how many numbers contain a given power of $2$?

-----Input-----
The input consists of a single line with two integers $n$ and $e$ ($0 \le n \le 9 \cdot 10^{18}, 0 \le e \le 62$).

-----Output-----
Output a single integer that is equal to the number of distinct integers $k$ ($0 \le k \le n$) whose decimal representation contains the digits of $2^e$ as a substring.

-----Examples-----
Sample Input 1:
1000000 1
Sample Output 1:
468559

Sample Input 2:
1000000 5
Sample Output 2:
49401

Sample Input 3:
1000000 16
Sample Output 3:
20

Sample Input 4:
9000000000000000000 62
Sample Output 4:
1

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