vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Recursive Queries

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Let us define two functions *f* and *g* on positive integer numbers. 

 

You need to process *Q* queries. In each query, you will be given three integers *l*, *r* and *k*. You need to print the number of integers *x* between *l* and *r* inclusive, such that *g*(*x*)<==<=*k*.

Input Specification:
The first line of the input contains an integer *Q* (1<=≤<=*Q*<=≤<=2<=×<=105) representing the number of queries. 

*Q* lines follow, each of which contains 3 integers *l*, *r* and *k* (1<=≤<=*l*<=≤<=*r*<=≤<=106,<=1<=≤<=*k*<=≤<=9).

Output Specification:
For each query, print a single line containing the answer for that query.

Demo Input:
['4\n22 73 9\n45 64 6\n47 55 7\n2 62 4\n', '4\n82 94 6\n56 67 4\n28 59 9\n39 74 4\n']

Demo Output:
['1\n4\n0\n8\n', '3\n1\n1\n5\n']

Note:
In the first example:
 -  *g*(33) = 9 as *g*(33) = *g*(3 × 3) = *g*(9) = 9 -  *g*(47) = *g*(48) = *g*(60) = *g*(61) = 6 -  There are no such integers between 47 and 55. -  *g*(4) = *g*(14) = *g*(22) = *g*(27) = *g*(39) = *g*(40) = *g*(41) = *g*(58) = 4

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a string *q*. A sequence of *k* strings *s*1,<=*s*2,<=...,<=*s**k* is called beautiful, if the concatenation of these strings is string *q* (formally, *s*1<=+<=*s*2<=+<=...<=+<=*s**k*<==<=*q*) and the first characters of these strings are distinct.

Find any beautiful sequence of strings or determine that the beautiful sequence doesn't exist.

Input Specification:
The first line contains a positive integer *k* (1<=≤<=*k*<=≤<=26) — the number of strings that should be in a beautiful sequence. 

The second line contains string *q*, consisting of lowercase Latin letters. The length of the string is within range from 1 to 100, inclusive.

Output Specification:
If such sequence doesn't exist, then print in a single line "NO" (without the quotes). Otherwise, print in the first line "YES" (without the quotes) and in the next *k* lines print the beautiful sequence of strings *s*1,<=*s*2,<=...,<=*s**k*.

If there are multiple possible answers, print any of them.

Demo Input:
['1\nabca\n', '2\naaacas\n', '4\nabc\n']

Demo Output:
['YES\nabca\n', 'YES\naaa\ncas\n', 'NO\n']

Note:
In the second sample there are two possible answers: {"*aaaca*", "*s*"} and {"*aaa*", "*cas*"}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are playing a puzzle game named petoris. It is played with a board divided into square grids and square tiles each of which fits to a single grid.

In each step of the game, you have a board partially filled with tiles. You also have a block consisting of several tiles. You are to place this block somewhere on the board or to discard it, under the following restrictions on placement:

* the block can be rotated, but cannot be divided nor flipped;
* no tiles of the block can collide with any tiles existing on the board; and
* all the tiles of the block need to be placed inside the board.



Your task is to write a program to find the maximum score you can earn in this step. Here, the score is the number of the horizontal lines fully filled with tiles after the block is placed, or -1 in case of discard.



Input

The first line of the input is N, the number of data sets. Then N data sets follow.

Each data set consists of lines describing a block and a board. Each description (both for a block and a board) starts with a line containing two integer H and W, the vertical and horizontal dimension. Then H lines follow, each with W characters, where a ‘#’ represents a tile and ‘.’ a vacancy. You can assume that 0 < H ≤ 64 and 0 < W ≤ 64. Each block consists of one or more tiles all of which are connected. Each board contains zero or more tiles, and has no horizontal line fully filled with tiles at the initial state.

Output

For each data set, print in a single line the maximum possible score.

Examples

Input

5
4 4
....
....
####
....
12 8
........
........
........
........
........
.......#
##.##..#
.#######
.#######
.#######
.#######
.####.#.
4 4
....
....
.###
...#
12 8
........
........
........
........
........
........
........
##...###
##.#####
#######.
#######.
#######.
4 4
####
#..#
#..#
####
12 8
........
........
........
........
........
.......#
##.##..#
##....##
##.##.##
##.##.##
##....##
.####.#.
2 2
##
#.
3 3
.##
.##
##.
4 4
....
.##.
.##.
....
2 2
..
..


Output

4
1
4
-1
2


Input

5
4 4
....
....

....
12 8
........
........
........
........
........
.......#
.##..#
.#######
.#######
.#######
.#######
.####.#.
4 4
....
....
.###
...#
12 8
........
........
........
........
........
........
........
...###
.#####
.
.
.
4 4

..#
..#

12 8
........
........
........
........
........
.......#
.##..#
....##
.##.##
.##.##
....##
.####.#.
2 2

.
3 3
.##
.##
.
4 4
....
.##.
.##.
....
2 2
..
..


Output

4
1
4
-1
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ilya got tired of sports programming, left university and got a job in the subway. He was given the task to determine the escalator load factor. 

Let's assume that n people stand in the queue for the escalator. At each second one of the two following possibilities takes place: either the first person in the queue enters the escalator with probability p, or the first person in the queue doesn't move with probability (1 - p), paralyzed by his fear of escalators and making the whole queue wait behind him.

Formally speaking, the i-th person in the queue cannot enter the escalator until people with indices from 1 to i - 1 inclusive enter it. In one second only one person can enter the escalator. The escalator is infinite, so if a person enters it, he never leaves it, that is he will be standing on the escalator at any following second. Ilya needs to count the expected value of the number of people standing on the escalator after t seconds. 

Your task is to help him solve this complicated task.


-----Input-----

The first line of the input contains three numbers n, p, t (1 ≤ n, t ≤ 2000, 0 ≤ p ≤ 1). Numbers n and t are integers, number p is real, given with exactly two digits after the decimal point.


-----Output-----

Print a single real number — the expected number of people who will be standing on the escalator after t seconds. The absolute or relative error mustn't exceed 10^{ - 6}.


-----Examples-----
Input
1 0.50 1

Output
0.5

Input
1 0.50 4

Output
0.9375

Input
4 0.20 2

Output
0.4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vishesh has gone to watch the new Spider-Man movie, but he is having troubles choosing which Popcorn-and-Coke combo to buy.

There are three combos A, B, and C available at the counter. You are given the time (in minute) for which each Popcorn bucket and Coke cup lasts. Given that Vishesh's satisfaction from a combo is defined as the total lasting time (in minute) of the Popcorn bucket and the Coke cup, find the maximum satisfaction he can get by buying a single combo.

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

- The first line of each input contains T - the number of test cases. The test cases then follow.
- The first line of each test case contains two space-separated integers A_{1} and A_{2}, meaning that for combo A, the Popcorn bucket lasts A_{1} minutes and the Coke cup lasts A_{2} minutes.
- The second line of each test case contains two space-separated integers B_{1} and B_{2}, meaning that for combo B, the Popcorn bucket lasts B_{1} minutes and the Coke cup lasts B_{2} minutes.
- The third line of each test case contains two space-separated integers C_{1} and C_{2}, meaning that for combo C, the Popcorn bucket lasts C_{1} minutes and the Coke cup lasts C_{2} minutes.

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

For each test case, output on a single line the maximum satisfaction Vishesh can get.

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

$1 ≤ T ≤ 1000$
$1 ≤ A_{1}, A_{2}, B_{1}, B_{2}, C_{1}, C_{2} ≤ 10^{9}$

----- Sample Input 1 ------ 
3
3 6
5 10
8 7
99 1
55 55
33 51
54 146
5436 627
1527 5421

----- Sample Output 1 ------ 
15
110
6948

----- explanation 1 ------ 
- Test case $1$:
- For combo $A$, the Popcorn bucket lasts $3$ minutes, and the Coke cup lasts $6$ minutes, so Vishesh gets a satisfaction of $3 + 6 = 9$ if he buys this combo.
- For combo $B$, the Popcorn bucket lasts $5$ minutes, and the Coke cup lasts $10$ minutes, so Vishesh gets a satisfaction of $5 + 10 = 15$ if he buys this combo.
- For combo $C$, the Popcorn bucket lasts $8$ minutes, and the Coke cup lasts $7$ minutes, so Vishesh gets a satisfaction of $8 + 7 = 15$ if he buys this combo.

Therefore Vishesh's maximum satisfaction is $15$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a word w, rearrange the letters of w to construct another word s in such a way that s is lexicographic-ally greater than w. In case of multiple possible answers, find the lexicographic-ally smallest one.

Input Format

The first line of input contains t, the number of test cases. Each of the next t lines contains w.

Output Format

For each testcase, output a string lexicographically bigger than w in a separate line. In case of multiple possible answers, print the lexicographically smallest one, and if no answer exists, print no answer.

Constraints

1≤t≤105

1≤|w|≤100

w will contain only lower-case English letters and its length will not exceed 100.

SAMPLE INPUT
5
ab
bb
hefg
dhck
dkhc

SAMPLE OUTPUT
ba
no answer
hegf
dhkc
hcdk

Explanation

Test case 1:

There exists only one string greater than 'ab' which can be built by   rearranging  'ab'. That is 'ba'.

**Test case 2:**

Not possible to rearrange 'bb' and get a lexicographically greater string.

**Test case 3:**

'hegf' is the next string lexicographically greater than 'hefg'.

**Test case 4:**

'dhkc' is the next string lexicographically greater than 'dhck'.

**Test case 5:**

'hcdk' is the next string lexicographically greater than 'dkhc'.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Convert integers to binary as simple as that. You would be given an integer as a argument and you have to return its binary form.
To get an idea about how to convert a decimal number into a binary number, visit here.

**Notes**: negative numbers should be handled as two's complement; assume all numbers are integers stored using 4 bytes (or 32 bits) in any language.

Your output should ignore leading 0s.

So, for example:
```python
to_binary(3)=="11"
to_binary(-3)=="11111111111111111111111111111101"
```

*Be Ready for Large Numbers. Happy Coding ^_^*

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is a follow-up from my previous Kata which can be found here: http://www.codewars.com/kata/5476f4ca03810c0fc0000098

This time, for any given linear sequence, calculate the function [f(x)] and return it as a function in Javascript or Lambda/Block in Ruby.

For example:

```python
get_function([0, 1, 2, 3, 4])(5) => 5
get_function([0, 3, 6, 9, 12])(10) => 30
get_function([1, 4, 7, 10, 13])(20) => 61
```

Assumptions for this kata are:
```
The sequence argument will always contain 5 values equal to f(0) - f(4).
The function will always be in the format "nx +/- m", 'x +/- m', 'nx', 'x' or 'm'
If a non-linear sequence simply return 'Non-linear sequence' for javascript, ruby, and python. For C#, throw an ArgumentException.
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
$N$ persons visited a restaurant. The restaurant is open from 0 to $T$. The $i$-th person entered the restaurant at $l_i$ and left at $r_i$. Find the maximum number of persons during the business hours.

Constraints

* $ 1 \leq N \leq 10^5 $
* $ 1 \leq T \leq 10^5 $
* $ 0 \leq l_i < r_i \leq T $

Input

The input is given in the following format.

$N$ $T$
$l_1$ $r_1$
$l_2$ $r_2$
:
$l_N$ $r_N$

Output

Print the maximum number of persons in a line.

Examples

Input

6 10
0 2
1 3
2 6
3 8
4 10
5 10


Output

4


Input

2 2
0 1
1 2


Output

1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An infinitely long Line Chillland Collider (LCC) was built in Chillland. There are n pipes with coordinates x_i that are connected to LCC. When the experiment starts at time 0, i-th proton flies from the i-th pipe with speed v_i. It flies to the right with probability p_i and flies to the left with probability (1 - p_i). The duration of the experiment is determined as the time of the first collision of any two protons. In case there is no collision, the duration of the experiment is considered to be zero.

Find the expected value of the duration of the experiment.

<image>Illustration for the first example

Input

The first line of input contains one integer n — the number of pipes (1 ≤ n ≤ 10^5). Each of the following n lines contains three integers x_i, v_i, p_i — the coordinate of the i-th pipe, the speed of the i-th proton and the probability that the i-th proton flies to the right in percentage points (-10^9 ≤ x_i ≤ 10^9, 1 ≤ v ≤ 10^6, 0 ≤ p_i ≤ 100). It is guaranteed that all x_i are distinct and sorted in increasing order.

Output

It's possible to prove that the answer can always be represented as a fraction P/Q, where P is an integer and Q is a natural number not divisible by 998 244 353. In this case, print P ⋅ Q^{-1} modulo 998 244 353.

Examples

Input


2
1 1 100
3 1 0


Output


1


Input


3
7 10 0
9 4 86
14 5 100


Output


0


Input


4
6 4 50
11 25 50
13 16 50
15 8 50


Output


150902884

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The word `internationalization` is sometimes abbreviated to `i18n`. This comes from the fact that there are 18 letters between the first `i` and the last `n`.

You are given a string s of length at least 3 consisting of lowercase English letters. Abbreviate s in the same way.

Constraints

* 3 ≤ |s| ≤ 100 (|s| denotes the length of s.)
* s consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:


s


Output

Print the abbreviation of s.

Examples

Input

internationalization


Output

i18n


Input

smiles


Output

s4s


Input

xyz


Output

x1z

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Wall (Rampart)

Historian Professor JOI is studying the once-existing Kingdom of IOI.

According to past research, the IOI Kingdom was in the shape of a rectangle divided into squares with H rows and W columns. The capital of the IOI kingdom was walled for defense.

The walls surrounding the capital of the IOI Kingdom have the following shape. A value called size is fixed on the wall. A castle wall of size s (s ≥ 3) is the square area of ​​s × s minus the square area of ​​(s − 2) × (s − 2) other than the outer circumference.

According to the survey, the size of the wall surrounding the capital was L or more. It is also known that some squares in the IOI Kingdom did not have walls.

Professor JOI wants to know how many possible walls there are for further research.

Task

Create a program to find out how many possible walls are given, given the size of the IOI kingdom, the minimum size of the walls, and the masses that are known to have not existed. ..

input

Read the following data from standard input.

* On the first line, the integers H, W, L, P are written with a blank as a delimiter. This is because the IOI Kingdom has a rectangular shape divided into squares with H rows vertically and W columns horizontally, and the size of the wall is L or more, and it is known that the wall did not exist. Indicates that there is a P-mass.
* In the i-th line (1 ≤ i ≤ P) of the following P lines, the integers Ai and Bi are written separated by blanks. This means that it is known that there were no walls in the squares in the Ai row from the top and the Bi column from the left in the IOI kingdom.


output

Print an integer on one line to the standard output, which indicates how many possible walls are possible.

Limits

All input data satisfy the following conditions.

* 1 ≤ H ≤ 4 000.
* 1 ≤ W ≤ 4 000.
* 3 ≤ L ≤ H and 3 ≤ L ≤ W.
* 0 ≤ P ≤ 100 000.
* 1 ≤ Ai ≤ H (1 ≤ i ≤ P).
* 1 ≤ Bi ≤ W (1 ≤ i ≤ P).
* (Ai, Bi) ≠ (Aj, Bj) (1 ≤ i <j ≤ P).



Input / output example

Input example 1


5 5 3 2
twenty two
4 3


Output example 1


Four


In the case of this input example, the following four types of possible walls can be considered. However, the squares indicated by x are the squares for which it is known that the castle wall did not exist.

<image>


Input example 2


7 8 4 3
twenty two
3 7
6 5


Output example 2


13


Input example 3


4000 4000 1234 4
1161 3028
596 1892
3731 2606
702 1530


Output example 3


7050792912


The question text and the data used for the automatic referee are the question text and the test data for scoring, which are created and published by the Japan Committee for Information Olympics.





Example

Input

5 5 3 2
2 2
4 3


Output

4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A set is an unordered collection of elements without duplicate entries. 

When printed, iterated or converted into a sequence, its elements will appear in an arbitrary order.

Example

>>> print set()
set([])

>>> print set('HackerRank')
set(['a', 'c', 'e', 'H', 'k', 'n', 'r', 'R'])

>>> print set([1,2,1,2,3,4,5,6,0,9,12,22,3])
set([0, 1, 2, 3, 4, 5, 6, 9, 12, 22])

>>> print set((1,2,3,4,5,5))
set([1, 2, 3, 4, 5])

>>> print set(set(['H','a','c','k','e','r','r','a','n','k']))
set(['a', 'c', 'r', 'e', 'H', 'k', 'n'])

>>> print set({'Hacker' : 'DOSHI', 'Rank' : 616 })
set(['Hacker', 'Rank'])

>>> print set(enumerate(['H','a','c','k','e','r','r','a','n','k']))
set([(6, 'r'), (7, 'a'), (3, 'k'), (4, 'e'), (5, 'r'), (9, 'k'), (2, 'c'), (0, 'H'), (1, 'a'), (8, 'n')])

Basically, sets are used for membership testing and eliminating duplicate entries.

Task  

Now, let's use our knowledge of sets and help Mickey. 

Ms. Gabriel Williams is a botany professor at District College. One day, she asked her student Mickey to compute the average of all the plants with distinct heights in her greenhouse.

Formula used: $\textit{Average}=\dfrac{\textit{Sum ofDistinct Heights}}{\textit{Total Number of distinct Heights}}$

Function Description   

Complete the average function in the editor below.   

average has the following parameters:   

int arr: an array of integers    

Returns   

float: the resulting float value rounded to 3 places after the decimal   

Input Format

The first line contains the integer, $N$, the size of $\textbf{arr}$.

The second line contains the $N$ space-separated integers, $arr\left[i\right]$.

Constraints

$0<N\leq100$

Sample Input
STDIN                                       Function
-----                                       --------
10                                          arr[] size N = 10
161 182 161 154 176 170 167 171 170 174     arr = [161, 181, ..., 174]

Sample Output
169.375

Explanation

Here, set$([154,161,167,170,171,174,176,182])$ is the set containing the distinct heights. Using the sum() and len() functions, we can compute the average.

$\textit{Average}=\dfrac{1355}{8}=169.375$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke is giving cookies to his three goats.
He has two cookie tins. One contains A cookies, and the other contains B cookies. He can thus give A cookies, B cookies or A+B cookies to his goats (he cannot open the tins).
Your task is to determine whether Snuke can give cookies to his three goats so that each of them can have the same number of cookies.

-----Constraints-----
 - 1 \leq A,B \leq 100
 - Both A and B are integers.

-----Input-----
Input is given from Standard Input in the following format:
A B

-----Output-----
If it is possible to give cookies so that each of the three goats can have the same number of cookies, print Possible; otherwise, print Impossible.

-----Sample Input-----
4 5

-----Sample Output-----
Possible

If Snuke gives nine cookies, each of the three goats can have three cookies.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
RK and RG are best friends. They are very particular in maintaining their Swag Level. Now, RK and RG travel to a mysterious place. There they found n Swag Traits.

A Swag Trait is defined as an array of positive integers of some given size.

Now, RK and RG decided to increase their Swag Level by playing a game in which they take turns and RK always moves first. In his turn, RK removes an integer from the beginning of any non-empty SWAG Trait, and in RG’s turn, he removes an integer from the end of any non-empty SWAG trait. They keep on playing until all the SWAG traits are empty. 

Both of them want to maximize their SWAG Level. Considering both of them play optimally, you have to output two integers, the Swag Level of both RK and RG.

SWAG Level of a person is defined as the sum of the integers removed by the person from the SWAG Traits.

INPUT:

First line contains an integer T (1 ≤ T ≤ 100) representing the number of Test cases.

Each Test case contains an integer n (1 ≤ n ≤ 100), the number of SWAG Traits. 

Next n lines contain description of each SWAG Trait:

First integer in each line is ki (1 ≤ ki ≤ 100) the size of ith SWAG Trait. Next ki integers are the elements of the SWAG Trait. Each element is a positive integer less than or equal to 1000.

Output:

For each test case, output two space separated integers: the SWAG level of RK and the SWAG level of RG, considering they played optimally.

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

SAMPLE OUTPUT
12 6
12 13

Explanation

1st Test Case

RK removes 1, 3 and 8 (1+3+8=12) from the SWAG Traits. RG removes 2 and 4 (4+2=6) from the SWAG Traits.

2nd Test Case

Here,RK removes 7 and 5 (7+5=12) from the SWAG Traits. RG removes 8 and 5 (8+5=13) from the SWAG Traits.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a regular polygon with $n$ vertices labeled from $1$ to $n$ in counter-clockwise order. The triangulation of a given polygon is a set of triangles such that each vertex of each triangle is a vertex of the initial polygon, there is no pair of triangles such that their intersection has non-zero area, and the total area of all triangles is equal to the area of the given polygon. The weight of a triangulation is the sum of weigths of triangles it consists of, where the weight of a triagle is denoted as the product of labels of its vertices.

Calculate the minimum weight among all triangulations of the polygon.


-----Input-----

The first line contains single integer $n$ ($3 \le n \le 500$) — the number of vertices in the regular polygon.


-----Output-----

Print one integer — the minimum weight among all triangulations of the given polygon.


-----Examples-----
Input
3

Output
6

Input
4

Output
18



-----Note-----

According to Wiki: polygon triangulation is the decomposition of a polygonal area (simple polygon) $P$ into a set of triangles, i. e., finding a set of triangles with pairwise non-intersecting interiors whose union is $P$.

In the first example the polygon is a triangle, so we don't need to cut it further, so the answer is $1 \cdot 2 \cdot 3 = 6$.

In the second example the polygon is a rectangle, so it should be divided into two triangles. It's optimal to cut it using diagonal $1-3$ so answer is $1 \cdot 2 \cdot 3 + 1 \cdot 3 \cdot 4 = 6 + 12 = 18$.

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