vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Problem

Given the string $ S $ of length $ N $. Process the following query $ Q $ times.

Query
Let $ S [L: R] $ be a character string consisting of $ S $ from the $ L $ character to the $ R $ character (including both ends).
Represent $ S [L: R] $ as $ AXBXCX (1 \ leq | A |, | B |, | C |, | X |) $ using the appropriate strings $ A, B, C, X $ With that in mind, it prints the length of the longest of such $ X $.
However, if such $ X $ does not exist, 0 is output instead.

Constraints

The input satisfies the following conditions.

* $ 1 \ leq N, Q \ leq 2 \ times 10 ^ 5 $
* Each letter of $ S $ consists of a lowercase alphabet
* $ 1 \ leq L_i \ leq R_i \ leq N $

Input

The input is given in the following format.


$ N $ $ Q $
$ S $
$ L_1 $ $ R_1 $
$ L_2 $ $ R_2 $
$ \ vdots $
$ L_Q $ $ R_Q $


$ N, Q, L, R $ are all given as integers.
$ N $ and $ Q $ are given on the first line, separated by blanks.
The string $ S $ is given on the second line.
2 + $ i (1 \ leq i \ leq Q) $ L_i $ and $ R_i $ are given on the $ line separated by blanks. These represent $ L, R $ in the $ i $ th query.

Output

Print the longest $ X $ length on a single line for each query.

Examples

Input

12 3
itisansansan
1 12
5 12
6 7


Output

2
1
0


Input

20 2
sensanbyakusanjuusan
1 20
1 14


Output

3
1


Input

21 6
aaaabaaaabaaaaaaaaaab
1 21
10 21
10 18
4 16
11 21
1 6


Output

4
0
2
2
0
1

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

Christmas is coming, and your task is to build a custom Christmas tree with the specified characters and the specified height.

# Inputs:
- `chars`: the specified characters. 
- `n`: the specified height. A positive integer greater than 2.

# Output:
- A multiline string. Each line is separated by `\n`. A tree contains two parts: leaves and trunks. 

The leaves should be `n` rows. The first row fill in 1 char, the second row fill in 3 chars, and so on. A single space will be added between two adjust chars, and some of the necessary spaces will be added to the left side, to keep the shape of the tree. No space need to be added to the right side.

The trunk should be at least 1 unit height, it depends on the value of the `n`. The minimum value of n is 3, and the height of the tree trunk is 1 unit height. If `n` increased by 3, and the tree trunk increased by 1 unit. For example, when n is 3,4 or 5, trunk should be 1 row; when n is 6,7 or 8, trunk should be 2 row; and so on.

Still not understand the task? Look at the following example ;-)

# Examples

For `chars = "*@o" and n = 3`,the output should be:
```
  *
 @ o
* @ o
  |
```

For `chars = "*@o" and n = 6`,the output should be:
```
     *
    @ o
   * @ o
  * @ o *
 @ o * @ o
* @ o * @ o
     |
     |
```

For `chars = "1234" and n = 6`,the output should be:
```
     1
    2 3
   4 1 2
  3 4 1 2
 3 4 1 2 3
4 1 2 3 4 1
     |
     |
```

For `chars = "123456789" and n = 3`,the output should be:
```
  1
 2 3
4 5 6
  |
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given several queries. Each query consists of three integers $p$, $q$ and $b$. You need to answer whether the result of $p/q$ in notation with base $b$ is a finite fraction.

A fraction in notation with base $b$ is finite if it contains finite number of numerals after the decimal point. It is also possible that a fraction has zero numerals after the decimal point.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of queries.

Next $n$ lines contain queries, one per line. Each line contains three integers $p$, $q$, and $b$ ($0 \le p \le 10^{18}$, $1 \le q \le 10^{18}$, $2 \le b \le 10^{18}$). All numbers are given in notation with base $10$.


-----Output-----

For each question, in a separate line, print Finite if the fraction is finite and Infinite otherwise.


-----Examples-----
Input
2
6 12 10
4 3 10

Output
Finite
Infinite

Input
4
1 1 2
9 36 2
4 12 3
3 5 4

Output
Finite
Finite
Finite
Infinite



-----Note-----

$\frac{6}{12} = \frac{1}{2} = 0,5_{10}$

$\frac{4}{3} = 1,(3)_{10}$

$\frac{9}{36} = \frac{1}{4} = 0,01_2$

$\frac{4}{12} = \frac{1}{3} = 0,1_3$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is an integer sequence A of length N.
Find the number of the pairs of integers l and r (1 \leq l \leq r \leq N) that satisfy the following condition:
 - A_l\ xor\ A_{l+1}\ xor\ ...\ xor\ A_r = A_l\ +\ A_{l+1}\ +\ ...\ +\ A_r
Here, xor denotes the bitwise exclusive OR.
Definition of XOR
The XOR of integers c_1, c_2, ..., c_m is defined as follows:
 - Let the XOR be X. In the binary representation of X, the digit in the 2^k's place (0 \leq k; k is an integer) is 1 if there are an odd number of integers among c_1, c_2, ...c_m whose binary representation has 1 in the 2^k's place, and 0 if that number is even.
For example, let us compute the XOR of 3 and 5. The binary representation of 3 is 011, and the binary representation of 5 is 101, thus the XOR has the binary representation 110, that is, the XOR is 6.

-----Constraints-----
 - 1 \leq N \leq 2 \times 10^5
 - 0 \leq A_i < 2^{20}
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 A_2 ... A_N

-----Output-----
Print the number of the pairs of integers l and r (1 \leq l \leq r \leq N) that satisfy the condition.

-----Sample Input-----
4
2 5 4 6

-----Sample Output-----
5

(l,r)=(1,1),(2,2),(3,3),(4,4) clearly satisfy the condition.
(l,r)=(1,2) also satisfies the condition, since A_1\ xor\ A_2 = A_1\ +\ A_2 = 7.
There are no other pairs that satisfy the condition, so the answer is 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Timur has $n$ candies. The $i$-th candy has a quantity of sugar equal to $a_i$. So, by eating the $i$-th candy, Timur consumes a quantity of sugar equal to $a_i$.

Timur will ask you $q$ queries regarding his candies. For the $j$-th query you have to answer what is the minimum number of candies he needs to eat in order to reach a quantity of sugar greater than or equal to $x_j$ or print -1 if it's not possible to obtain such a quantity. In other words, you should print the minimum possible $k$ such that after eating $k$ candies, Timur consumes a quantity of sugar of at least $x_j$ or say that no possible $k$ exists.

Note that he can't eat the same candy twice and queries are independent of each other (Timur can use the same candy in different queries).


-----Input-----

The first line of input contains a single integer $t$ ($1 \leq t \leq 1000$)  — the number of test cases. The description of test cases follows.

The first line contains $2$ integers $n$ and $q$ ($1 \leq n, q \leq 1.5\cdot10^5$) — the number of candies Timur has and the number of queries you have to print an answer for respectively.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^4$) — the quantity of sugar in each of the candies respectively.

Then $q$ lines follow.

Each of the next $q$ lines contains a single integer $x_j$ ($1 \leq x_j \leq 2 \cdot 10^9$) – the quantity Timur wants to reach for the given query.

It is guaranteed that the sum of $n$ and the sum of $q$ over all test cases do not exceed $1.5 \cdot 10^5$.


-----Output-----

For each test case output $q$ lines. For the $j$-th line output the number of candies Timur needs to eat in order to reach a quantity of sugar greater than or equal to $x_j$ or print -1 if it's not possible to obtain such a quantity.


-----Examples-----

Input
3
8 7
4 3 3 1 1 4 5 9
1
10
50
14
15
22
30
4 1
1 2 3 4
3
1 2
5
4
6
Output
1
2
-1
2
3
4
8
1
1
-1


-----Note-----

For the first test case:

For the first query, Timur can eat any candy, and he will reach the desired quantity.

For the second query, Timur can reach a quantity of at least $10$ by eating the $7$-th and the $8$-th candies, thus consuming a quantity of sugar equal to $14$.

For the third query, there is no possible answer.

For the fourth query, Timur can reach a quantity of at least $14$ by eating the $7$-th and the $8$-th candies, thus consuming a quantity of sugar equal to $14$.

For the second test case:

For the only query of the second test case, we can choose the third candy from which Timur receives exactly $3$ sugar. It's also possible to obtain the same answer by choosing the fourth candy.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef likes to play with big numbers. Today, he has a big positive integer N. He can select any two digits from this number (the digits can be same but their positions should be different) and orders them in any one of the two possible ways. For each of these ways, he creates a two digit number from it (might contain leading zeros). Then, he will pick a character corresponding to the ASCII value equal to this number, i.e. the number 65 corresponds to 'A', 66 to 'B' and so on till 90 for 'Z'. Chef is only interested in finding which of the characters in the range 'A' to 'Z' can possibly be picked this way. 

-----Input-----
The first line of the input contains an integer T denoting the number of test cases.
The first line of the input contains an integer N. 

-----Output-----
For each test case, output a string containing characters Chef can pick in sorted order If the resulting size of string is zero, you should output a new line.

-----Constraints-----
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 10100000

-----Subtasks-----
- Subtask #1 (40 points) N ≤ 1010
- Subtask #2 (60 points) Original Constraints

-----Example-----
Input:
4
65
566
11
1623455078

Output:
A
AB

ACDFGHIJKLNPQRSTUVW

-----Explanation-----
Example case 1. Chef can pick digits 6 and 5 and create integers 56 and 65. The integer 65 corresponds to 'A'.
Example case 2. Chef can pick digits 6 and 5 and create 'A' as it equals 65. He can pick 6 and 6 (they are picked from position 2 and position 3, respectively) to create 'B' too. Hence answer is "AB".
Example case 3. It's not possible to create any character from 'A' to 'Z'. Hence, we just print a new line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A permutation is a sequence of integers p_1, p_2, ..., p_{n}, consisting of n distinct positive integers, each of them doesn't exceed n. Let's denote the i-th element of permutation p as p_{i}. We'll call number n the size of permutation p_1, p_2, ..., p_{n}.

Nickolas adores permutations. He likes some permutations more than the others. He calls such permutations perfect. A perfect permutation is such permutation p that for any i (1 ≤ i ≤ n) (n is the permutation size) the following equations hold p_{p}_{i} = i and p_{i} ≠ i. Nickolas asks you to print any perfect permutation of size n for the given n.


-----Input-----

A single line contains a single integer n (1 ≤ n ≤ 100) — the permutation size.


-----Output-----

If a perfect permutation of size n doesn't exist, print a single integer -1. Otherwise print n distinct integers from 1 to n, p_1, p_2, ..., p_{n} — permutation p, that is perfect. Separate printed numbers by whitespaces.


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

Output
-1

Input
2

Output
2 1 

Input
4

Output
2 1 4 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
## MTV Cribs is back!

![](https://s-media-cache-ak0.pinimg.com/236x/1b/cf/f4/1bcff4f4621644461103576e40bde4ed.jpg)

_If you haven't solved it already I recommend trying [this kata](https://www.codewars.com/kata/5834a44e44ff289b5a000075) first._

## Task

Given `n` representing the number of floors build a penthouse like this:

```
        ___
       /___\                
      /_____\
      |  _  |     1 floor
      |_|_|_|
      
       _____
      /_____\
     /_______\
    /_________\             
   /___________\
   |           |
   |    ___    |     2 floors
   |   |   |   |
   |___|___|___|
 
      _______
     /_______\
    /_________\
   /___________\
  /_____________\
 /_______________\
/_________________\
|                 |         3 floors
|                 |
|      _____      |
|     |     |     |
|     |     |     |
|_____|_____|_____|

```

**Note:** whitespace should be preserved on both sides of the roof. No invalid input tests.

Good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an even digit number N, partition the number into multiple numbers of two digits. For ex: if he chooses 1345 then he parts the number into 13 and 45. Calculate the product of these two digit numbers modulo (10^{9}+7).
 
Example 1:
Input:
N = 2222
Output:
484
Explanation:
2222 is divided into 22 and 22.
So, the result is 484.
Example 2:
Input:
N = 10
Output:
10
Explanation:
10 can be divided into only 10
so the result is 10. 
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function prodTwoDigit() which takes an Integer N as input and returns the product of two digit numbers when N is divided.
 
Expected Time Complexity: O(log_{100}N)
Expected Auxiliary Space: O(1)
 
Constraints:
2 <= N <= 10^{18}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Find out the maximum sub-array of non negative numbers from an array. 

The sub-array should be continuous. That is, a sub-array created by choosing the second and fourth element and skipping the third element is invalid.

Maximum sub-array is defined in terms of the sum of the elements in the sub-array. Sub-array A is greater than sub-array B if sum(A) > sum(B).

NOTE 1 :If there is a tie, then compare with segment's length and return segment which has maximum length 

NOTE 2: If there is still a tie, then return the segment with minimum starting index.

-----Input-----

The first line contains the number of test cases. Each test cases contains an integer N. next line consists of N integers, the elements of the array.

-----Output-----

Print out the maximum sub-array as stated above.

-----Constraints-----
-  1  ≤  T  ≤  100 
-  1  ≤  N  ≤  105 
-  1  ≤  Ai  ≤  105 

-----Example-----
Input:

1
6
1 2 5 -7 2 3

Output:

1 2 5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tom is an upcoming senior undergraduate student planning for his courses for the final year. The final year will have two semesters, in which there are $n$ courses offered numbered from $1$ to $n$. Course $i$ has a difficulty level $d_ i$. Two courses may be on a same topic but are at different levels: Level I or Level II. For example, there may be Calculus I and Calculus II offered. In this case, Level I and Level II are two different courses, and Level I is a prerequisite of Level II. Tom can only take Level II in the second semester if he takes Level I in the first semester. He does not necessarily need to take Level II after taking Level I.

To satisfy his graduation requirement, Tom needs to take $k$ courses in total in his last year. Tom would not want to spend too much time studying for courses, as the last year before graduation can be very busy. He therefore would like the sum of difficulties of all courses he takes to be as small as possible. Given that many courses Tom struggles to figure out a good course schedule. Can you help him?

-----Input-----
The first line of the input has two integers $n$ and $k$ ($1 \leq k \leq n \leq 2 \cdot 10^5$). Each of the next $n$ lines has a string and a positive integer. The $i$th line describes the name of course $i$ and its difficulty $d_ i$. All difficulties are no larger than $10^6$. All course names contain at least one and no more than $20$ lowercase English letters. A course name can be optionally followed by a trailing digit ‘1’ or ‘2’ that denotes that it is a Level I or Level II course. It is guaranteed that if the input contains a Level I course, then it also contains its corresponding Level II course, and vice versa. It is also guaranteed that if a course name has two levels, then there does not exist another course with a same name but without levels.

-----Output-----
Output the minimum sum of difficulties of the $k$ courses that Tom can take in the last year.

-----Examples-----
Sample Input:
5 2
linearalgebra 10
calculus1 10
calculus2 20
honorsanalysis1 50
honorsanalysis2 100
Sample Output:
20

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As meticulous Gerald sets the table and caring Alexander sends the postcards, Sergey makes snowmen. Each showman should consist of three snowballs: a big one, a medium one and a small one. Sergey's twins help him: they've already made n snowballs with radii equal to r1, r2, ..., rn. To make a snowman, one needs any three snowballs whose radii are pairwise different. For example, the balls with radii 1, 2 and 3 can be used to make a snowman but 2, 2, 3 or 2, 2, 2 cannot. Help Sergey and his twins to determine what maximum number of snowmen they can make from those snowballs.

Input

The first line contains integer n (1 ≤ n ≤ 105) — the number of snowballs. The next line contains n integers — the balls' radii r1, r2, ..., rn (1 ≤ ri ≤ 109). The balls' radii can coincide.

Output

Print on the first line a single number k — the maximum number of the snowmen. Next k lines should contain the snowmen's descriptions. The description of each snowman should consist of three space-separated numbers — the big ball's radius, the medium ball's radius and the small ball's radius. It is allowed to print the snowmen in any order. If there are several solutions, print any of them.

Examples

Input

7
1 2 3 4 5 6 7


Output

2
3 2 1
6 5 4


Input

3
2 2 3


Output

0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Imagine you have a rooted tree consisting of $n$ vertices. Consider the following function:

int order[n]; // initially consists of -1
int pointer = 0;
void dfs(int vertex, int depth) {
  order[pointer] = depth;
  pointer++;
  for each child of vertex
    dfs(child, depth + 1);
}

In the end this function produces an array ${order}[]$. We will call an array suitable if and only if it can be produced as a result of running $dfs(root,0)$ on a rooted tree with $n$ vertices. 

You are given an array ${a}$, whose elements are either question signs or integer numbers. How many suitable arrays can you get, if you are allowed to replace any question sign with non-negative integer number? Print this number modulo $10^9+7$.

Input Format  

The first line contains a single integer $n$, that is the size of array ${a}$. The next line contains $n$ elements of the array: $a[0],a[1],...,a[n-1]$. Each element is either a question sign, or a non-negative integer number which doesn't exceed ${200}$.  

Constraints 

$1\leq n\leq10^5$ 

$0\leq a[i]\leq200$

Output Format

Print a single integer $-$ the number of suitable arrays you can get modulo $10^9+7$.

Sample Input #0

3
? ? ?    

Sample Output #0

2

Sample Input #1

2
1 ?

Sample Output #1

0

Sample Input #2

4
0 ? 1 ?

Sample Output #2

2

Explanation

In sample#0 there are two possible arrays: [0, 1, 2] and [0, 1, 1];

In sample#1 there cannot be any suitable arrays, because each of them starts with 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a positive decimal number x.

Your task is to convert it to the "simple exponential notation".

Let x = a·10b, where 1 ≤ a < 10, then in general case the "simple exponential notation" looks like "aEb". If b equals to zero, the part "Eb" should be skipped. If a is an integer, it should be written without decimal point. Also there should not be extra zeroes in a and b.

Input

The only line contains the positive decimal number x. The length of the line will not exceed 106. Note that you are given too large number, so you can't use standard built-in data types "float", "double" and other.

Output

Print the only line — the "simple exponential notation" of the given number x.

Examples

Input

16


Output

1.6E1


Input

01.23400


Output

1.234


Input

.100


Output

1E-1


Input

100.


Output

1E2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An ironman triathlon is a race where participants swim for $3.86$ km, ride a bicycle for $180.25$ km, and finally run a marathon, and it is considered one of the toughest sport events. Viveka has been training for an even more challenging competition: the $n$-athlon. In an $n$-athlon race, participants have to go from the starting point to the finishing point through several types of terrain: water, sand, ice, asphalt, etc. To make the race more interesting, participants are free to pick the route that they think suits best their abilities. Last year Viveka achieved an epic victory by skating the last $40$ km in $1$ hour over ice, while her arch-rival Veronica was stuck in a tar pit $1$ m from the finishing point.

The terrain distribution for this year has been published and now it is your task as the optimization expert in Viveka’s team to help her figure out the best route for the race. The competition takes place in a flat area, which we model as the 2D plane, and each type of terrain is shaped as a horizontal strip. Participants are not allowed to leave the race area. You know the position of each strip and Viveka’s speed in that type of terrain.

-----Input-----
The first line contains two pairs of decimal numbers $x_ s$, $y_ s$, $x_ f$, $y_ f$, the $x$ and $y$ coordinates of the starting and finishing point, respectively, in meters. The second line contains one integer $n$ ($1 \leq n \leq 10000$), the number of layers. The third line contains $n-1$ decimal numbers, the $y$ coordinate of each change between layers. Layers are given in order, that is, $y_ s < y_1 < y_2 < \cdots < y_{n-1} < y_ f$, so the shape of layer $i$ is $(-10000,10000)\times (y_{i-1},y_{i})$. The first and last layers extend only until the $y$ coordinate of the starting and finishing point, this is they have shape $(-10000,10000)\times (y_ s,y_1)$ and $(-10000,10000)\times (y_{n-1},y_ f)$ respectively. The fourth line contains $n$ decimal numbers, Viveka’s speed in each layer, in meters per second. All decimal numbers have absolute value at most $10^4$ and at most $4$ decimals.

-----Output-----
Output the minimum time required for Viveka to go from the starting to the finishing point. Your answer should be within absolute or relative error at most $10^{-6}$.

-----Examples-----
Sample Input:
0 0 0 100
2
50
5 1
Sample Output:
60

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