vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Ross, Chandler and Joey are best friends. One day they went to pond and Joey suggest them to play the game "Bamboozle". In this game they have N balls with each numbered from 0-9, but first ball is numbered from 1-9. Ross tells sub-strings 'S' formed by those balls and Chandler throws S stones into the pond. At last, Joey have to tell total how many stones Chandler throw in to the pond, 'T'.

But Joey is poor in maths, So help Joey to win the game and make bamboozle of Chandler and Ross.

NOTE: The answer can be very large, Joey to tell T%(10^9+7) instead. 

INPUT

A single line containing a string of numbers that appear on the first, second, third ball and so on.

OUTPUT

A single line which is the total number of stones that Chandler throws in to the pond, T%(1000000007).

Constraints

1 ≤ N ≤ 200000

SAMPLE INPUT
16

SAMPLE OUTPUT
23

Explanation

The sub-string of number 16 are 16, 1 and 6 whose sum is 23.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pussycat Sonya has N blocks consisting of integers. You may assume that block is a one-dimensional array. She wants to put them all in the box of length M in such a way that they don't overlap. To do this she's allowed to remove any number of leftmost or rightmost elements in some blocks. It's also allowed to remove block completely or to not remove anything at all.

What is the maximal sum of elements in the box Sonya can get? Pay attention on that she's allowed to leave some free space in the box if she wants.

Input:
The first line of input contains two integers N - the number of blocks and M - the length of the box.
The next N lines describe the blocks. The first number in i-th of these lines is leni - the length of the i-th block. Then leni integers follow - the elements of the i-th block.

Output:
Print the maximal sum of elements in the box Sonya can get.

Constraints:
1 ≤ N ≤ 100
1 ≤ M ≤ 1000
-10^9 ≤ element of block ≤ 10^9
0 ≤ sum overall leni ≤ 10^5

SAMPLE INPUT
3 4
3 2 3 5
2 7 -1
2 8 10

SAMPLE OUTPUT
30

Explanation

Sonya has 3 blocks: {2, 3, 5}, {7, -1}, {8, 10} and a box of length 4. The best strategy is:
delete two leftmost elements in the 1-st block {2, 3, 5} => {5}
delete the rightmost element in the 2-nd block {7, -1} => {7}
Now the blocks look like: {5}, {7}, {8, 10}, and Sonya can put them all in the box. The sum of elements in the box is 30.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Seryozha conducts a course dedicated to building a map of heights of Stepanovo recreation center. He laid a rectangle grid of size n × m cells on a map (rows of grid are numbered from 1 to n from north to south, and columns are numbered from 1 to m from west to east). After that he measured the average height of each cell above Rybinsk sea level and obtained a matrix of heights of size n × m. The cell (i, j) lies on the intersection of the i-th row and the j-th column and has height h_{i, j}. 

Seryozha is going to look at the result of his work in the browser. The screen of Seryozha's laptop can fit a subrectangle of size a × b of matrix of heights (1 ≤ a ≤ n, 1 ≤ b ≤ m). Seryozha tries to decide how the weather can affect the recreation center — for example, if it rains, where all the rainwater will gather. To do so, he is going to find the cell having minimum height among all cells that are shown on the screen of his laptop.

Help Seryozha to calculate the sum of heights of such cells for all possible subrectangles he can see on his screen. In other words, you have to calculate the sum of minimum heights in submatrices of size a × b with top left corners in (i, j) over all 1 ≤ i ≤ n - a + 1 and 1 ≤ j ≤ m - b + 1.

Consider the sequence g_i = (g_{i - 1} ⋅ x + y) mod z. You are given integers g_0, x, y and z. By miraculous coincidence, h_{i, j} = g_{(i - 1) ⋅ m + j - 1} ((i - 1) ⋅ m + j - 1 is the index).

Input

The first line of the input contains four integers n, m, a and b (1 ≤ n, m ≤ 3 000, 1 ≤ a ≤ n, 1 ≤ b ≤ m) — the number of rows and columns in the matrix Seryozha has, and the number of rows and columns that can be shown on the screen of the laptop, respectively.

The second line of the input contains four integers g_0, x, y and z (0 ≤ g_0, x, y < z ≤ 10^9).

Output

Print a single integer — the answer to the problem.

Example

Input


3 4 2 1
1 2 3 59


Output


111

Note

The matrix from the first example: 

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Republic of AtCoder, Snuke Chameleons (Family: Chamaeleonidae, Genus: Bartaberia) are very popular pets. Ringo keeps N Snuke Chameleons in a cage.

A Snuke Chameleon that has not eaten anything is blue. It changes its color according to the following rules:

* A Snuke Chameleon that is blue will change its color to red when the number of red balls it has eaten becomes strictly larger than the number of blue balls it has eaten.
* A Snuke Chameleon that is red will change its color to blue when the number of blue balls it has eaten becomes strictly larger than the number of red balls it has eaten.



Initially, every Snuke Chameleon had not eaten anything. Ringo fed them by repeating the following process K times:

* Grab either a red ball or a blue ball.
* Throw that ball into the cage. Then, one of the chameleons eats it.



After Ringo threw in K balls, all the chameleons were red. We are interested in the possible ways Ringo could have thrown in K balls. How many such ways are there? Find the count modulo 998244353. Here, two ways to throw in balls are considered different when there exists i such that the color of the ball that are thrown in the i-th throw is different.

Constraints

* 1 \leq N,K \leq 5 \times 10^5
* N and K are integers.

Input

Input is given from Standard Input in the following format:


N K


Output

Print the possible ways Ringo could have thrown in K balls, modulo 998244353.

Examples

Input

2 4


Output

7


Input

3 7


Output

57


Input

8 3


Output

0


Input

8 10


Output

46


Input

123456 234567


Output

857617983

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nowadays, most of the internet advertisements are not statically linked to a web page. Instead, what will be shown to the person opening a web page is determined within 100 milliseconds after the web page is opened. Usually, multiple companies compete for each ad slot on the web page in an auction. Each of them receives a request with details about the user, web page and ad slot and they have to respond within those 100 milliseconds with a bid they would pay for putting an advertisement on that ad slot. The company that suggests the highest bid wins the auction and gets to place its advertisement. If there are several companies tied for the highest bid, the winner gets picked at random.

However, the company that won the auction does not have to pay the exact amount of its bid. In most of the cases, a second-price auction is used. This means that the amount paid by the company is equal to the maximum of all the other bids placed for this ad slot.

Let's consider one such bidding. There are n companies competing for placing an ad. The i-th of these companies will bid an integer number of microdollars equiprobably randomly chosen from the range between L_{i} and R_{i}, inclusive. In the other words, the value of the i-th company bid can be any integer from the range [L_{i}, R_{i}] with the same probability. 

Determine the expected value that the winner will have to pay in a second-price auction.


-----Input-----

The first line of input contains an integer number n (2 ≤ n ≤ 5). n lines follow, the i-th of them containing two numbers L_{i} and R_{i} (1 ≤ L_{i} ≤ R_{i} ≤ 10000) describing the i-th company's bid preferences.

This problem doesn't have subproblems. You will get 8 points for the correct submission.


-----Output-----

Output the answer with absolute or relative error no more than 1e - 9.


-----Examples-----
Input
3
4 7
8 10
5 5

Output
5.7500000000

Input
3
2 5
3 4
1 6

Output
3.5000000000



-----Note-----

Consider the first example. The first company bids a random integer number of microdollars in range [4, 7]; the second company bids between 8 and 10, and the third company bids 5 microdollars. The second company will win regardless of the exact value it bids, however the price it will pay depends on the value of first company's bid. With probability 0.5 the first company will bid at most 5 microdollars, and the second-highest price of the whole auction will be 5. With probability 0.25 it will bid 6 microdollars, and with probability 0.25 it will bid 7 microdollars. Thus, the expected value the second company will have to pay is 0.5·5 + 0.25·6 + 0.25·7 = 5.75.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are developing a project to build a new data center. The data center will be a rectangle with an area of exactly n square meters. Each side of the data center must be an integer.

Your goal is to minimize the impact of the external environment on the data center. For this reason, you want to minimize the length of the perimeter of the data center (that is, the sum of the lengths of its four sides).

What is the minimum perimeter of a rectangular data center with an area of exactly n square meters, if the lengths of all its sides must be integers?

Input

The first and only line of the input contains an integer n (1 ≤ n ≤ 10^5), where n is the area of the data center in square meters.

Output

Print the required minimum perimeter in meters.

Examples

Input


36


Output


24


Input


13


Output


28


Input


1


Output


4

Note

In the first example, the required shape of the data center is 6×6 square. Its area is 36 and the perimeter is 6+6+6+6=24.

In the second example, the required shape of the data center is 1×13 rectangle. Its area is 13 and the perimeter is 1+13+1+13=28.

In the third example, the required shape of the data center is 1×1 square. Its area is 1 and the perimeter is 1+1+1+1=4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider an infinite chessboard and a special knight whose move types can change given power-ups. The knight is trying to reach square $(0, 0)$.

Some of the squares of the infinite chessboard have tarot cards on them. If the knight lands on some position $(r, c)$ on the infinite chessboard with a tarot card on it, then the knight has the option of buying that card at that position. Each tarot card will have a price, and will have two integer values written on it. The tarot card with values $a$ and $b$ written on it allow the knight to make relative jumps:$(-a, -b)\qquad (a, -b)\qquad (-a, b)\qquad (a, b)\qquad (b, a)\qquad (-b, a)\qquad (b, -a)\qquad (-b, -a)$

The knight retains all cards he purchases and can make relative moves from any of the cards he owns any number of times. The knight must only pay when obtaining cards and can perform jumps at no additional cost. For example, if he buys a card with $3$ and $2$ and another card with $8$ and $4$, he may jump by $(-2, 3)$, and from there jump by $(8, 4)$, and later jump by $(-3, 2)$. Of course, he cannot make a jump $(a,b)$ until after he arrives at a square with a tarot card with $a$ and $b$ on it, and purchases that card.

Given positions of the tarot cards on the board and their prices, find the least amount that the knight must pay to reach square $(0, 0)$.

-----Input-----
Each test case will begin with a line containing a single integer $n$ ($1\! \le \! n\! \le \! 1000$), which is the number of tarot cards on the chessboard.

Each of the next $n$ lines contains a description of a tarot card in five space-separated integers:$r$ $c$ $a$ $b$ $p$

($-10^9\! \le \! r, c\! \le \! 10^9, 1\! \le \! a, b, p\! \le \! 10^9$), where $(r,c)$ is the location of the tarot card, $a$ and $b$ are the offset values, and $p$ is the price of the card.

The first tarot card is the initial position of the knight. Multiple tarot cards may exist at the same location. The knight must have a tarot card to move.

-----Output-----
Output a single integer, which is the minimum cost for the knight to reach the goal at $(0,0)$. Output $-1$ if it is not possible to reach the goal.

-----Examples-----
Sample Input 1:
2
3 3 2 2 100
1 1 1 1 500
Sample Output 1:
600

Sample Input 2:
2
2 0 2 1 100
6 0 8 1 1
Sample Output 2:
100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp wants to assemble his own keyboard. Layouts with multiple rows are too complicated for him — his keyboard will consist of only one row, where all $26$ lowercase Latin letters will be arranged in some order.

Polycarp uses the same password $s$ on all websites where he is registered (it is bad, but he doesn't care). He wants to assemble a keyboard that will allow to type this password very easily. He doesn't like to move his fingers while typing the password, so, for each pair of adjacent characters in $s$, they should be adjacent on the keyboard. For example, if the password is abacaba, then the layout cabdefghi... is perfect, since characters a and c are adjacent on the keyboard, and a and b are adjacent on the keyboard. It is guaranteed that there are no two adjacent equal characters in $s$, so, for example, the password cannot be password (two characters s are adjacent).

Can you help Polycarp with choosing the perfect layout of the keyboard, if it is possible?


-----Input-----

The first line contains one integer $T$ ($1 \le T \le 1000$) — the number of test cases.

Then $T$ lines follow, each containing one string $s$ ($1 \le |s| \le 200$) representing the test case. $s$ consists of lowercase Latin letters only. There are no two adjacent equal characters in $s$.


-----Output-----

For each test case, do the following:

  if it is impossible to assemble a perfect keyboard, print NO (in upper case, it matters in this problem);  otherwise, print YES (in upper case), and then a string consisting of $26$ lowercase Latin letters — the perfect layout. Each Latin letter should appear in this string exactly once. If there are multiple answers, print any of them. 


-----Example-----
Input
5
ababa
codedoca
abcda
zxzytyz
abcdefghijklmnopqrstuvwxyza

Output
YES
bacdefghijklmnopqrstuvwxyz
YES
edocabfghijklmnpqrstuvwxyz
NO
YES
xzytabcdefghijklmnopqrsuvw
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ivan has got an array of n non-negative integers a_1, a_2, ..., a_{n}. Ivan knows that the array is sorted in the non-decreasing order. 

Ivan wrote out integers 2^{a}_1, 2^{a}_2, ..., 2^{a}_{n} on a piece of paper. Now he wonders, what minimum number of integers of form 2^{b} (b ≥ 0) need to be added to the piece of paper so that the sum of all integers written on the paper equalled 2^{v} - 1 for some integer v (v ≥ 0). 

Help Ivan, find the required quantity of numbers.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5). The second input line contains n space-separated integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 2·10^9). It is guaranteed that a_1 ≤ a_2 ≤ ... ≤ a_{n}.


-----Output-----

Print a single integer — the answer to the problem.


-----Examples-----
Input
4
0 1 1 1

Output
0

Input
1
3

Output
3



-----Note-----

In the first sample you do not need to add anything, the sum of numbers already equals 2^3 - 1 = 7.

In the second sample you need to add numbers 2^0, 2^1, 2^2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are organising a king of the hill tournament, the Buenos Aires Paddleboarding Competition (BAPC), with $n$ participants. In a king of the hill tournament, one person starts as a “king” and is then challenged by another person, the winning person becomes the new king. This is repeated until all participants have challenged exactly once (except for the starting person). In a paddleboarding match, there are no draws. The person which ends up as king, wins the tournament. Since you are the organiser, you get to choose the starting person and the order in which they challenge the king.

Someone is offering you a substantial amount of money in case one of the participants, Henk, ends up winning the tournament. You happen to know, for any two participants $x$ and $y$, which of the two would win if they were to match during the tournament. Consequently, you choose to do the unethical: you will try to rig the game. Can you find a schedule that makes Henk win the tournament?

-----Input-----
 - The first line contains an integer $1 \leq n \leq 1000$, the number of participants. The participants are numbered $0, \dots , n-1$, where Henk is $0$.
 - Then $n$ lines follow, where each line has exactly $n$ characters (not counting the newline character). These lines represent the matrix with the information of who beats who, as follows. On line $i$ the $j$th character is (note that $0 \leq i, j < n$):
 - ’1’ if person $i$ will win against person $j$.
 - ’0’ if person $i$ will lose against person $j$.
 - ’X’ if $i = j$.

-----Output-----
Print a sequence of participants, such that the first person starts as king and the consequent participants challenge the king. If there is no way to rig the game such that Henk wins, print “impossible”.

-----Examples-----
Sample Input:
3
X10
0X1
10X
Sample Output:
1 2 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nowadays, most of the internet advertisements are not statically linked to a web page. Instead, what will be shown to the person opening a web page is determined within 100 milliseconds after the web page is opened. Usually, multiple companies compete for each ad slot on the web page in an auction. Each of them receives a request with details about the user, web page and ad slot and they have to respond within those 100 milliseconds with a bid they would pay for putting an advertisement on that ad slot. The company that suggests the highest bid wins the auction and gets to place its advertisement. If there are several companies tied for the highest bid, the winner gets picked at random.

However, the company that won the auction does not have to pay the exact amount of its bid. In most of the cases, a second-price auction is used. This means that the amount paid by the company is equal to the maximum of all the other bids placed for this ad slot.

Let's consider one such bidding. There are n companies competing for placing an ad. The i-th of these companies will bid an integer number of microdollars equiprobably randomly chosen from the range between Li and Ri, inclusive. In the other words, the value of the i-th company bid can be any integer from the range [Li, Ri] with the same probability. 

Determine the expected value that the winner will have to pay in a second-price auction.

Input

The first line of input contains an integer number n (2 ≤ n ≤ 5). n lines follow, the i-th of them containing two numbers Li and Ri (1 ≤ Li ≤ Ri ≤ 10000) describing the i-th company's bid preferences.

This problem doesn't have subproblems. You will get 8 points for the correct submission.

Output

Output the answer with absolute or relative error no more than 1e - 9.

Examples

Input

3
4 7
8 10
5 5


Output

5.7500000000


Input

3
2 5
3 4
1 6


Output

3.5000000000

Note

Consider the first example. The first company bids a random integer number of microdollars in range [4, 7]; the second company bids between 8 and 10, and the third company bids 5 microdollars. The second company will win regardless of the exact value it bids, however the price it will pay depends on the value of first company's bid. With probability 0.5 the first company will bid at most 5 microdollars, and the second-highest price of the whole auction will be 5. With probability 0.25 it will bid 6 microdollars, and with probability 0.25 it will bid 7 microdollars. Thus, the expected value the second company will have to pay is 0.5·5 + 0.25·6 + 0.25·7 = 5.75.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S of length N containing only numeric characters, find the number of Nice Pairs.

A Nice Pair is a pair of indices - (i, j) such that 1 ≤ i < j ≤ N and j - i = |S_{j} - S_{i}|.

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

- First line will contain T, number of testcases. Then the testcases follow.
- The first line of each testcase contains a single integer, N, the length of the string
- The second line of each testcase contains a string S of length N. The string contains only numeric characters [0-9]

------ Output Format ------ 

For each testcase, output a single integer - the number of nice pairs in the given string.

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

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 10^{5}$
- String $S$ contains only numeric characters
- The sum of $N$ over all test cases does not exceed $2\cdot10^{5}$

----- Sample Input 1 ------ 
3
3
123
5
13492
8
94241234

----- Sample Output 1 ------ 
3
2
9

----- explanation 1 ------ 
Test Case $1$: There are $3$ nice pairs in the given string - $(1,2) , (1,3) , (2,3)$

Test Case $2$: There are $2$ nice pairs in the given string - $(2,3) , (3,5)$

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
A triangular number is the number of dots in an equilateral triangle uniformly filled with dots. For example, three dots can be arranged in a triangle; thus three is a triangular number. The *n*-th triangular number is the number of dots in a triangle with *n* dots on a side. . You can learn more about these numbers from Wikipedia (http://en.wikipedia.org/wiki/Triangular_number).

Your task is to find out if a given integer is a triangular number.

Input Specification:
The first line contains the single number *n* (1<=≤<=*n*<=≤<=500) — the given integer.

Output Specification:
If the given integer is a triangular number output YES, otherwise output NO.

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

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After playing with her beautiful array, Mishka decided to learn some math. After learning how to multiply, divide and what is divisibility, she is now interested in solving the following problem.

You are given integer k and array a1, a2, ..., an of n integers. You are to find non-empty subsequence of array elements such that the product of its elements is divisible by k and it contains minimum possible number of elements.

Formally, you are to find a sequence of indices 1 ≤ i1 < i2 < ... < im ≤ n such that <image> is divisible by k while m is minimum possible among all such variants.

If there are more than one such subsequences, you should choose one among them, such that sum of its elements is minimum possible.

Mishka quickly solved this problem. Will you do so?

Input

The first line of the input contains two integers n and k (1 ≤ n ≤ 1 000, 1 ≤ k ≤ 1012).

The second line of the input contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1012) — array elements.

Output

Print single positive integer m in the first line — the number of elements in desired sequence.

In the second line print m distinct integers — the sequence of indices of given array elements, which should be taken into the desired sequence. 

If there are more than one such subsequence (e.g. subsequence of minimum possible number of elements and with minimum possible sum of elements), you can print any of them.

If there are no such subsequences, print  - 1 in the only line.

Example

Input

5 60
2 4 6 5 2


Output

3
4 3 1 

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