vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Two players called $\mathbf{P1}$ and $\textbf{P2}$ are playing a game with a starting number of stones. Player $1$ always plays first, and the two players move in alternating turns. The game's rules are as follows:

In a single move, a player can remove either $2$, $3$, or $5$ stones from the game board. 
If a player is unable to make a move, that player loses the game.

Given the starting number of stones, find and print the name of the winner.  $\mathbf{P1}$ is named First and $\textbf{P2}$ is named Second.  Each player plays optimally, meaning they will not make a move that causes them to lose the game if a winning move exists.

For example, if $n=4$, $\mathbf{P1}$ can make the following moves:  

$\mathbf{P1}$ removes $2$ stones leaving $2$. $\textbf{P2}$ will then remove $2$ stones and win.
$\mathbf{P1}$ removes $3$ stones leaving $1$. $\textbf{P2}$ cannot move and loses.

$\mathbf{P1}$ would make the second play and win the game.

Function Description

Complete the gameOfStones function in the editor below.  It should return a string, either First or Second.  

gameOfStones has the following parameter(s):

n: an integer that represents the starting number of stones

Input Format

The first line contains an integer $\boldsymbol{\boldsymbol{t}}$, the number of test cases. 

Each of the next $\boldsymbol{\boldsymbol{t}}$ lines contains an integer $n$, the number of stones in a test case.

Constraints

$1\le n,t\le100$

Output Format

On a new line for each test case, print First if the first player is the winner.  Otherwise print Second.

Sample Input
8
1
2
3
4
5
6
7
10

Sample Output
Second
First
First
First
First
First
Second
First

Explanation

In the sample, we have $t=8$ testcases.  

If $n=1$, $\mathbf{P1}$ can't make any moves and loses the game.

If $n=2$, $\mathbf{P1}$ removes $2$ stones and wins the game.

If $n=3$, $\mathbf{P1}$ removes $2$ stones in their first move, leaving $1$ stone on the board and winning the game.  

If $n=4$, $\mathbf{P1}$ removes $3$ stones in their first move, leaving $1$ stone on the board and winning the game.  

If $n=5$, $\mathbf{P1}$ removes all $5$ stones from the game board, winning the game.  

If $n=6$, $\mathbf{P1}$ removes $5$ stones in their first move, leaving $1$ stone on the board and winning the game.  

If $n=7$, $\mathbf{P1}$ can make any of the following three moves:

Remove $2$ stones, leaving $5$ stones on the board. $\textbf{P2}$ then removes $5$ stones, winning the game.  
Remove $3$ stones, leaving $4$ stones on the board. $\textbf{P2}$ then removes $3$ stones, leaving $1$ stone left on the board and winning the game.  
Remove $5$ stones, leaving $2$ stones on the board. $\textbf{P2}$ then removes the $2$ remaining stones and wins the game.  

All possible moves result in $\textbf{P2}$ winning.

If $n=10$, $\mathbf{P1}$ can remove either $2$ or $3$ stones to win the game.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The ugliness of a sequence of size N is defined as the number of pairs of neighboring elements which are not equal to each other. Formally, the ugliness of a sequence increase by 1 if for a value of i, 2 ≤ i ≤ N, the following condition holds true:
A_{i} \neq A_{i-1}.

Examples: 
[1, 2, 2, 3], ugliness is 2.
[2, 1, 2, 3,4], ugliness is 4.

You are given a sequence A of length N consisting of the first K natural numbers only. Each of the first K natural numbers occur at least once in the given sequence. For each value of K, you are supposed to remove all of its occurrences from the original sequence and determine the ugliness of the resulting sequence.

Note:  An empty sequence has ugliness of 0.

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

- First line will contain T, the number of test cases. Then the testcases follow.
- Each testcase consist of two lines of input
- First line contains two integers N, K 
- Second line contains N space-separated integers, where the i^{th} integer denotes the i^{th} element of the sequence A.

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

- For each testcase print K space-separated integers denoting the answer for that testcase.

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

$1 ≤ T ≤ 1000$
$1 ≤ K ≤ N ≤ 10^{5}$
- For each $i$, $1 ≤ A_{i} ≤ K$
- Every number from $1$ to  $K$ appears atleast once
- Sum of N over all cases doesn't exceed $10^{5}$

----- Sample Input 1 ------ 
2
8 2
1 2 1 2 2 2 1 2
8 3
1 2 2 1 1 1 2 3
----- Sample Output 1 ------ 
0 0
1 1 3

----- explanation 1 ------ 
Test case 1:
- By removing 1, we get the sequence: $[2, 2, 2, 2, 2]$. Since all the elements are the same, ugliness is $0$
- By removing 2, we get the sequence: $[1, 1, 1]$. Since all the elements are the same, ugliness is $0$

Test case 2:
- By removing 1, we get the sequence: $[2, 2, 2, 3]$. Since the 3rd and 4th elements are not equal, ugliness is $1$.
- By removing 2, we get the sequence: $[1, 1, 1, 1, 3]$. Since the 3rd and 4th elements are not equal, ugliness is $1$.
- By removing 3, we get the sequence: $[1, 2, 2, 1, 1, 1, 2]$. Since 1st and 2nd, 3rd and 4th, 6th and 7th are not equal, total ugliness is $3$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The length of the longest common prefix of two strings s=s_1 s_2 … s_n and t = t_1 t_2 … t_m is defined as the maximum k ≤ min(n, m) such that s_1 s_2 … s_k equals t_1 t_2 … t_k. Let's denote the longest common prefix of two strings s and t as lcp(s,t).

Z-function of a string s_1 s_2 ... s_n is a sequence of integers z_1, z_2, …, z_n, where z_i = lcp(s_1 s_2 … s_n,\ \ s_i s_{i+1} ... s_n). Ж-function of a string s is defined as z_1 + z_2 + … + z_n.

You're given a string s=s_1 s_2 … s_n and q queries. Each query is described by two integers l_i and r_i, where 1 ≤ l_i ≤ r_i ≤ n. The answer for the query is defined as Ж-function of the string s_{l_i} s_{l_i +1} … s_{r_i}.

Input

The first line contains the string s, consisting of lowercase English letters (1 ≤ |s| ≤ 200 000). The second line contains one integer q — the number of queries (1 ≤ q ≤ 200 000). Each of the following q lines contains two integers l_i and r_i, describing the query (1 ≤ l_i ≤ r_i ≤ |s|).

Output

For every query output one integer: the value of Ж-function of the corresponding substring.

Examples

Input


abbd
4
2 3
1 3
3 3
1 4


Output


3
3
1
4


Input


bbaaa
5
2 4
1 5
1 5
3 3
1 2


Output


3
6
6
1
3

Note

In the first sample case there are four queries:

  * the first query corresponds to the substring bb, and its Ж-function equals 2 + 1 = 3;
  * the second query corresponds to the substring abb, and its Ж-function equals 3 + 0 + 0 = 3;
  * the third query corresponds to the substring b, and its Ж-function equals 1.
  * the fourth query corresponds to the substring abdd, and its Ж-function equals 4 + 0 + 0 + 0= 4. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Professor Snape has lots of potions. Bottles containing all types of potions are stacked on shelves which cover the entire wall from floor to ceiling. Professor Snape has broken his bones several times while climbing the top shelf for retrieving a potion. He decided to get a ladder for him. But he has no time to visit Diagon Alley. So he instructed Ron Weasley to make a ladder for him. Professor Snape specifically wants a step ladder which looks like an inverted 'V' from side view.
Professor just mentioned two things before vanishing-

B - separation between left side (LS) and right side (RS) on the ground
LS - the length of left side

What should be the length of RS? At one extreme LS can be vertical and at other RS can be vertical. Ron is angry and confused. Since Harry is busy battling Voldemort, its your duty to help him find the minimum and maximum length of RS.

Input
First line contains single integer T, the number of test cases. Then T lines follow each containing 2 integers - B and LS.

Output
Output T lines, each containing minimum value of RS and maximum value of RS, separated by space. The answer (RS) will be considered correct if it has relative and absolute error less than 10^-2.

Constraints
1 ≤ T ≤ 10001 ≤ B < LS ≤ 1000

Example

Input:
3
4 5
10 12
10 20

Output:
3.0 6.40312
6.63325 15.6205
17.3205 22.3607

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke has a fair N-sided die that shows the integers from 1 to N with equal probability and a fair coin. He will play the following game with them:
 - Throw the die. The current score is the result of the die.
 - As long as the score is between 1 and K-1 (inclusive), keep flipping the coin. The score is doubled each time the coin lands heads up, and the score becomes 0 if the coin lands tails up.
 - The game ends when the score becomes 0 or becomes K or above. Snuke wins if the score is K or above, and loses if the score is 0.
You are given N and K. Find the probability that Snuke wins the game.

-----Constraints-----
 - 1 ≤ N ≤ 10^5
 - 1 ≤ K ≤ 10^5
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N K

-----Output-----
Print the probability that Snuke wins the game. The output is considered correct when the absolute or relative error is at most 10^{-9}.

-----Sample Input-----
3 10

-----Sample Output-----
0.145833333333

 - If the die shows 1, Snuke needs to get four consecutive heads from four coin flips to obtain a score of 10 or above. The probability of this happening is \frac{1}{3} \times (\frac{1}{2})^4 = \frac{1}{48}.
 - If the die shows 2, Snuke needs to get three consecutive heads from three coin flips to obtain a score of 10 or above. The probability of this happening is \frac{1}{3} \times (\frac{1}{2})^3 = \frac{1}{24}.
 - If the die shows 3, Snuke needs to get two consecutive heads from two coin flips to obtain a score of 10 or above. The probability of this happening is \frac{1}{3} \times (\frac{1}{2})^2 = \frac{1}{12}.
Thus, the probability that Snuke wins is \frac{1}{48} + \frac{1}{24} + \frac{1}{12} = \frac{7}{48} \simeq 0.1458333333.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is the new king of the country Chefland. As first and most important responsibility he wants to reconstruct the road system of Chefland. There are N (1 to N) cities in the country and each city i has a population Pi. Chef wants to build some bi-directional roads connecting different cities such that each city is connected to every other city (by a direct road or through some other intermediate city) and starting from any city one can visit every other city in the country through these roads. Cost of building a road between two cities u and v is Pu x Pv. Cost to build the road system is the sum of cost of every individual road that would be built. 
Help king Chef to find the minimum cost to build the new road system in Chefland such that every city is connected to each other.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. 
First line contains an integer N denoting the number of cities in the country. Second line contains N space separated integers Pi, the population of i-th city.

-----Output-----
For each test case, print a single integer, the minimum cost to build the new road system on separate line.

-----Constraints-----
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 105
- 1 ≤ Pi ≤ 106

-----Example-----
Input:
2
2
5 10
4
15 10 7 13

Output:
50
266

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given three integers, A, B and C.

Among them, two are the same, but the remaining one is different from the rest.

For example, when A=5,B=7,C=5, A and C are the same, but B is different.

Find the one that is different from the rest among the given three integers.  

-----Constraints-----
 - -100 \leq A,B,C \leq 100 
 - A, B and C are integers.
 - The input satisfies the condition in the statement.

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

-----Output-----
Among A, B and C, print the integer that is different from the rest.

-----Sample Input-----
5 7 5

-----Sample Output-----
7

This is the same case as the one in the statement.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Pikachu had an array with him. He wrote down all the non-empty subsequences of the array on paper. Note that an array of size *n* has 2*n*<=-<=1 non-empty subsequences in it. 

Pikachu being mischievous as he always is, removed all the subsequences in which Maximum_element_of_the_subsequence <=-<= Minimum_element_of_subsequence <=≥<=*d*

Pikachu was finally left with *X* subsequences. 

However, he lost the initial array he had, and now is in serious trouble. He still remembers the numbers *X* and *d*. He now wants you to construct any such array which will satisfy the above conditions. All the numbers in the final array should be positive integers less than 1018. 

Note the number of elements in the output array should not be more than 104. If no answer is possible, print <=-<=1.

Input Specification:
The only line of input consists of two space separated integers *X* and *d* (1<=≤<=*X*,<=*d*<=≤<=109).

Output Specification:
Output should consist of two lines.

First line should contain a single integer *n* (1<=≤<=*n*<=≤<=10<=000)— the number of integers in the final array.

Second line should consist of *n* space separated integers — *a*1,<=*a*2,<=... ,<=*a**n* (1<=≤<=*a**i*<=&lt;<=1018).

If there is no answer, print a single integer -1. If there are multiple answers, print any of them.

Demo Input:
['10 5\n', '4 2\n']

Demo Output:
['6\n5 50 7 15 6 100', '4\n10 100 1000 10000']

Note:
In the output of the first example case, the remaining subsequences after removing those with Maximum_element_of_the_subsequence  -  Minimum_element_of_subsequence  ≥ 5 are [5], [5, 7], [5, 6], [5, 7, 6], [50], [7], [7, 6], [15], [6], [100]. There are 10 of them. Hence, the array [5, 50, 7, 15, 6, 100] is valid.

Similarly, in the output of the second example case, the remaining sub-sequences after removing those with Maximum_element_of_the_subsequence  -  Minimum_element_of_subsequence  ≥ 2 are [10], [100], [1000], [10000]. There are 4 of them. Hence, the array [10, 100, 1000, 10000] is valid.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
In a medieval kingdom, the economic crisis is raging. Milk drops fall, Economic indicators are deteriorating every day, money from the treasury disappear. To remedy the situation, King Charles Sunnyface decided make his *n* sons-princes marry the brides with as big dowry as possible.

In search of candidates, the king asked neighboring kingdoms, and after a while several delegations arrived with *m* unmarried princesses. Receiving guests, Karl learned that the dowry of the *i* th princess is *w**i* of golden coins. 

Although the action takes place in the Middle Ages, progressive ideas are widespread in society, according to which no one can force a princess to marry a prince whom she does not like. Therefore, each princess has an opportunity to choose two princes, for each of which she is ready to become a wife. The princes were less fortunate, they will obey the will of their father in the matter of choosing a bride.

Knowing the value of the dowry and the preferences of each princess, Charles wants to play weddings in such a way that the total dowry of the brides of all his sons would be as great as possible. At the same time to marry all the princes or princesses is not necessary. Each prince can marry no more than one princess, and vice versa, each princess can marry no more than one prince.

Help the king to organize the marriage of his sons in the most profitable way for the treasury.

Input Specification:
The first line contains two integers *n*, *m* (2<=≤<=*n*<=≤<=200<=000, 1<=≤<=*m*<=≤<=200<=000) — number of princes and princesses respectively.

Each of following *m* lines contains three integers *a**i*, *b**i*, *w**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*, *a**i*<=≠<=*b**i*, 1<=≤<=*w**i*<=≤<=10<=000) — number of princes, which *i*-th princess is ready to marry and the value of her dowry.

Output Specification:
Print the only integer — the maximum number of gold coins that a king can get by playing the right weddings.

Demo Input:
['2 3\n1 2 5\n1 2 1\n2 1 10\n', '3 2\n1 2 10\n3 2 20\n']

Demo Output:
['15', '30']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Timofey and a tree

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Each New Year Timofey and his friends cut down a tree of *n* vertices and bring it home. After that they paint all the *n* its vertices, so that the *i*-th vertex gets color *c**i*.

Now it's time for Timofey birthday, and his mother asked him to remove the tree. Timofey removes the tree in the following way: he takes some vertex in hands, while all the other vertices move down so that the tree becomes rooted at the chosen vertex. After that Timofey brings the tree to a trash can.

Timofey doesn't like it when many colors are mixing together. A subtree annoys him if there are vertices of different color in it. Timofey wants to find a vertex which he should take in hands so that there are no subtrees that annoy him. He doesn't consider the whole tree as a subtree since he can't see the color of the root vertex.

A subtree of some vertex is a subgraph containing that vertex and all its descendants.

Your task is to determine if there is a vertex, taking which in hands Timofey wouldn't be annoyed.

Input Specification:
The first line contains single integer *n* (2<=≤<=*n*<=≤<=105) — the number of vertices in the tree.

Each of the next *n*<=-<=1 lines contains two integers *u* and *v* (1<=≤<=*u*,<=*v*<=≤<=*n*, *u*<=≠<=*v*), denoting there is an edge between vertices *u* and *v*. It is guaranteed that the given graph is a tree.

The next line contains *n* integers *c*1,<=*c*2,<=...,<=*c**n* (1<=≤<=*c**i*<=≤<=105), denoting the colors of the vertices.

Output Specification:
Print "NO" in a single line, if Timofey can't take the tree in such a way that it doesn't annoy him.

Otherwise print "YES" in the first line. In the second line print the index of the vertex which Timofey should take in hands. If there are multiple answers, print any of them.

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

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For the grand opening of the algorithmic games in NlogNsglow, a row of tower blocks is set to be demolished in a grand demonstration of renewal. Originally the plan was to accomplish this with controlled explosions, one for each tower block, but time constraints now require a hastier solution.

To help you remove the blocks more rapidly you have been given the use of a Universal Kinetic / Incandescent Energy Particle Cannon (UKIEPC). On a single charge, this cutting-edge contraption can remove either all of the floors in a single tower block, or all the $x$-th floors in all the blocks simultaneously, for user’s choice of the floor number $x$. In the latter case, the blocks that are less than $x$ floors high are left untouched, while for blocks having more than $x$ floors, all the floors above the removed $x$-th one fall down by one level.

-----Task-----
Given the number of floors of all towers, output the minimum number of charges needed to eliminate all floors of all blocks.

-----Input-----
The first line of input contains the number of blocks $n$, where $2 \leq n \leq 100000$. The second line contains $n$ consecutive block heights $h_ i$ for $i=1,2,\ldots ,n$, where $1 \leq h_ i \leq 1000000$.

-----Output-----
Output one line containing one integer: the minimum number of charges needed to tear down all the blocks.

-----Examples-----
Sample Input:
6
2 1 8 8 2 3
Sample Output:
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A mad scientist Dr.Jubal has made a competitive programming task. Try to solve it!

You are given integers $n,k$. Construct a grid $A$ with size $n \times n$ consisting of integers $0$ and $1$. The very important condition should be satisfied: the sum of all elements in the grid is exactly $k$. In other words, the number of $1$ in the grid is equal to $k$.

Let's define:  $A_{i,j}$ as the integer in the $i$-th row and the $j$-th column.  $R_i = A_{i,1}+A_{i,2}+...+A_{i,n}$ (for all $1 \le i \le n$).  $C_j = A_{1,j}+A_{2,j}+...+A_{n,j}$ (for all $1 \le j \le n$).  In other words, $R_i$ are row sums and $C_j$ are column sums of the grid $A$.  For the grid $A$ let's define the value $f(A) = (\max(R)-\min(R))^2 + (\max(C)-\min(C))^2$ (here for an integer sequence $X$ we define $\max(X)$ as the maximum value in $X$ and $\min(X)$ as the minimum value in $X$). 

Find any grid $A$, which satisfies the following condition. Among such grids find any, for which the value $f(A)$ is the minimum possible. Among such tables, you can find any.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. Next $t$ lines contain descriptions of test cases.

For each test case the only line contains two integers $n$, $k$ $(1 \le n \le 300, 0 \le k \le n^2)$.

It is guaranteed that the sum of $n^2$ for all test cases does not exceed $10^5$.


-----Output-----

For each test case, firstly print the minimum possible value of $f(A)$ among all tables, for which the condition is satisfied.

After that, print $n$ lines contain $n$ characters each. The $j$-th character in the $i$-th line should be equal to $A_{i,j}$.

If there are multiple answers you can print any.


-----Example-----
Input
4
2 2
3 8
1 0
4 16

Output
0
10
01
2
111
111
101
0
0
0
1111
1111
1111
1111



-----Note-----

In the first test case, the sum of all elements in the grid is equal to $2$, so the condition is satisfied. $R_1 = 1, R_2 = 1$ and $C_1 = 1, C_2 = 1$. Then, $f(A) = (1-1)^2 + (1-1)^2 = 0$, which is the minimum possible value of $f(A)$.

In the second test case, the sum of all elements in the grid is equal to $8$, so the condition is satisfied. $R_1 = 3, R_2 = 3, R_3 = 2$ and $C_1 = 3, C_2 = 2, C_3 = 3$. Then, $f(A) = (3-2)^2 + (3-2)^2 = 2$. It can be proven, that it is the minimum possible value of $f(A)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of numbers, return a string made up of four parts:

a) a four character 'word', made up of the characters derived from the first two and last two numbers in the array. order should be as read left to right (first, second, second last, last),

b) the same as above, post sorting the array into ascending order,

c) the same as above, post sorting the array into descending order,

d) the same as above, post converting the array into ASCII characters and sorting alphabetically.

The four parts should form a single string, each part separated by a hyphen: '-'

example format of solution: 'asdf-tyui-ujng-wedg'

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