vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A gene is represented as a string of length $n$ (where $n$ is divisible by $4$), composed of the letters $\mbox{A}$, $\mbox{C}$, $\textbf{T}$, and $\mbox{G}$.
It is considered to be steady if each of the four letters occurs exactly $\frac{n}{4}$ times.  For example, $\textbf{GACT}$ and $\textbf{AAGTGCCT}$ are both steady genes.

Bear Limak is a famous biotechnology scientist who specializes in modifying bear DNA to make it steady.  Right now, he is examining a gene represented as a string $\textit{gene}$.  It is not necessarily steady.  Fortunately, Limak can choose one (maybe empty) substring of $\textit{gene}$ and replace it with any string of the same length.

Modifying a large substring of bear genes can be dangerous.
Given a string $\textit{gene}$, can you help Limak find the length of the smallest possible substring that he can replace to make $\textit{gene}$ a steady gene?

Note: A substring of a string $\boldsymbol{\mathrm{~S~}}$ is a subsequence made up of zero or more contiguous characters of $\boldsymbol{\mathrm{~S~}}$.

As an example, consider $\textit{gene}=\textit{ACTGAAAG}$.  The substring $\boldsymbol{AA}$ just before or after $\mbox{G}$ can be replaced with $\textit{CT}$ or $\boldsymbol{TC}$.  One selection would create $\textbf{ACTGACTG}$.

Function Description

Complete the $\textit{steadyGene}$ function in the editor below.  It should return an integer that represents the length of the smallest substring to replace.  

steadyGene has the following parameter:  

gene: a string

Input Format

The first line contains an interger $n$ divisible by $4$, that denotes the length of a string $\textit{gene}$. 

The second line contains a string $\textit{gene}$ of length $n$.

Constraints

$4\leq n\leq500000$  
$n$ is divisible by $4$  
$gene[i]\in[CGAT]$  

Subtask  

$4\leq n\leq2000$ in tests worth $30\%$ points.

Output Format

Print the length of the minimum length substring that can be replaced to make $\textit{gene}$ stable.

Sample Input
8  
GAAATAAA

Sample Output
5

Explanation

One optimal solution is to replace $\textbf{AAATA}$ with $\textbf{TTCCG}$ resulting in $\textbf{GTTCCGAA}$. 

The replaced substring has length $5$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: New Year and Entity Enumeration

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given an integer *m*.

Let *M*<==<=2*m*<=-<=1.

You are also given a set of *n* integers denoted as the set *T*. The integers will be provided in base 2 as *n* binary strings of length *m*.

A set of integers *S* is called "good" if the following hold. 
 1.  If , then . 1.  If , then  1.   1.  All elements of *S* are less than or equal to *M*. 
Here,  and  refer to the bitwise XOR and bitwise AND operators, respectively.

Count the number of good sets *S*, modulo 109<=+<=7.

Input Specification:
The first line will contain two integers *m* and *n* (1<=≤<=*m*<=≤<=1<=000, 1<=≤<=*n*<=≤<=*min*(2*m*,<=50)).

The next *n* lines will contain the elements of *T*. Each line will contain exactly *m* zeros and ones. Elements of *T* will be distinct.

Output Specification:
Print a single integer, the number of good sets modulo 109<=+<=7.

Demo Input:
['5 3\n11010\n00101\n11000\n', '30 2\n010101010101010010101010101010\n110110110110110011011011011011\n']

Demo Output:
['4\n', '860616440\n']

Note:
An example of a valid set *S* is {00000, 00101, 00010, 00111, 11000, 11010, 11101, 11111}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Gargi is thinking of a solution to a problem. Meanwhile, her friend asks her to solve another problem. Since Gargi is busy in her own problem, she seeks your help to solve the new problem.

You are given a string S containing characters a-z (lower case letters) only. You need to change the string to a new string consisting of only one letter from a-z.

For a given character S[i] in the string, if you change it to a character having lower ASCII value than the character S[i], you gain points equal to the difference in ASCII value of the old character and the new character. Similarly, for a given character S[j] in the string, if you change it to a character having higher ASCII value than the character S[j], you lose points equal to the difference in ASCII value of the old character and the new character.

However, Gargi does not like gaining or losing points. She has asked you to change the string in such a way that the total losing or gaining of points at the end of the string conversion is minimum.

Give Gargi the absolute value of the points you have at the end of the string conversion.

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

The first line of each of the T test case contains a string S containing only lower case characters (a-z)

-----Output-----
For each test case, output a single line containing the answer.

-----Constraints-----
- 1 ≤ T ≤ 10
- 1 ≤ |S| ≤ 100000

-----Example-----
Input:
1
abba

Output:
2

-----Explanation-----
Example case 1. The new string can be aaaa where you have +2 points at the end of string conversion or it can be bbbb where you have -2 points at the end of string conversion. Hence the output is 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Give you N cards. Only one natural number is written on each card. However, the same number is never written.

From now on, as a question, I will say an appropriate natural number. Please answer the largest remainder you get when you divide the number on the card you have by the number I said.

For example, suppose you have three cards with 9, 3, and 8, respectively. If I say "4", find the remainder of 9 and 3 and 8 divided by 4, respectively. The remainders are 1, 3, and 0, respectively, but the largest remainder is 3, so 3 is the correct answer.

Let's get started. e? Is it hard to have a lot of cards? It can not be helped. Now let's use the computer to find the largest remainder. Create a program that finds the largest of the remainders of the number on the card divided by the number asked. Ask the question many times, not just once, but never ask the same number more than once.



input

The input consists of one dataset. Input data is given in the following format.


N Q
c1 c2 ... cN
q1
q2
::
qQ


The number of cards N (2 ≤ N ≤ 300000) and the number of questions Q (2 ≤ Q ≤ 100000) are given in the first line, separated by one space, and the number ci (1 ≤ 100000) written on the card in the second line. ci ≤ 300000) is given with one space delimiter. The following Q line is given the number qi (1 ≤ qi ≤ 300000) given as a question.

output

Output the maximum remainder on one line for each question.

Example

Input

3 3
9 3 8
4
6
5


Output

3
3
4

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One day three best friends Petya, Vasya and Tonya decided to form a team and take part in programming contests. Participants are usually offered several problems during programming contests. Long before the start the friends decided that they will implement a problem if at least two of them are sure about the solution. Otherwise, the friends won't write the problem's solution.

This contest offers *n* problems to the participants. For each problem we know, which friend is sure about the solution. Help the friends find the number of problems for which they will write a solution.

Input Specification:
The first input line contains a single integer *n* (1<=≤<=*n*<=≤<=1000) — the number of problems in the contest. Then *n* lines contain three integers each, each integer is either 0 or 1. If the first number in the line equals 1, then Petya is sure about the problem's solution, otherwise he isn't sure. The second number shows Vasya's view on the solution, the third number shows Tonya's view. The numbers on the lines are separated by spaces.

Output Specification:
Print a single integer — the number of problems the friends will implement on the contest.

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

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

Note:
In the first sample Petya and Vasya are sure that they know how to solve the first problem and all three of them know how to solve the second problem. That means that they will write solutions for these problems. Only Petya is sure about the solution for the third problem, but that isn't enough, so the friends won't take it. 

In the second sample the friends will only implement the second problem, as Vasya and Tonya are sure about the solution.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Text Document Analysis

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Modern text editors usually show some information regarding the document being edited. For example, the number of words, the number of pages, or the number of characters.

In this problem you should implement the similar functionality.

You are given a string which only consists of:
 -  uppercase and lowercase English letters, -  underscore symbols (they are used as separators), -  parentheses (both opening and closing). 
It is guaranteed that each opening parenthesis has a succeeding closing parenthesis. Similarly, each closing parentheses has a preceding opening parentheses matching it. For each pair of matching parentheses there are no other parenthesis between them. In other words, each parenthesis in the string belongs to a matching "opening-closing" pair, and such pairs can't be nested.

For example, the following string is valid: "_Hello_Vasya(and_Petya)__bye_(and_OK)".

Word is a maximal sequence of consecutive letters, i.e. such sequence that the first character to the left and the first character to the right of it is an underscore, a parenthesis, or it just does not exist. For example, the string above consists of seven words: "Hello", "Vasya", "and", "Petya", "bye", "and" and "OK". Write a program that finds:
 -  the length of the longest word outside the parentheses (print 0, if there is no word outside the parentheses), -  the number of words inside the parentheses (print 0, if there is no word inside the parentheses).

Input Specification:
The first line of the input contains a single integer *n* (1<=≤<=*n*<=≤<=255) — the length of the given string. The second line contains the string consisting of only lowercase and uppercase English letters, parentheses and underscore symbols.

Output Specification:
Print two space-separated integers:
 -  the length of the longest word outside the parentheses (print 0, if there is no word outside the parentheses), -  the number of words inside the parentheses (print 0, if there is no word inside the parentheses).

Demo Input:
['37\n_Hello_Vasya(and_Petya)__bye_(and_OK)\n', '37\n_a_(_b___c)__de_f(g_)__h__i(j_k_l)m__\n', '27\n(LoooonG)__shOrt__(LoooonG)\n', '5\n(___)\n']

Demo Output:
['5 4', '2 6', '5 2', '0 0\n']

Note:
In the first sample, the words "Hello", "Vasya" and "bye" are outside any of the parentheses, and the words "and", "Petya", "and" and "OK" are inside. Note, that the word "and" is given twice and you should count it twice in the answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Hide-and-seek is a children’s game. Players hide here and there, and one player called it tries to find all the other players.

Now you played it and found all the players, so it’s turn to hide from it. Since you have got tired of running around for finding players, you don’t want to play it again. So you are going to hide yourself at the place as far as possible from it. But where is that?

Your task is to find the place and calculate the maximum possible distance from it to the place to hide.



Input

The input contains a number of test cases.

The first line of each test case contains a positive integer N (N ≤ 1000). The following N lines give the map where hide-and-seek is played. The map consists of N corridors. Each line contains four real numbers x1, y1, x2, and y2, where (x1, y1 ) and (x2, y2 ) indicate the two end points of the corridor. All corridors are straight, and their widths are negligible. After these N lines, there is a line containing two real numbers sx and sy, indicating the position of it. You can hide at an arbitrary place of any corridor, and it always walks along corridors. Numbers in the same line are separated by a single space.

It is guaranteed that its starting position (sx, sy) is located on some corridor and linked to all corridors directly or indirectly.

The end of the input is indicated by a line containing a single zero.

Output

For each test case, output a line containing the distance along the corridors from ‘it”s starting position to the farthest position. The value may contain an error less than or equal to 0.001. You may print any number of digits below the decimal point.

Example

Input

2
0 0 3 3
0 4 3 1
1 1
0


Output

4.243

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Suppose you have a string S which has length N and is indexed from 0 to N−1. String R is the reverse of the string S. The string S is funny if the condition |Si−Si−1|=|Ri−Ri−1| is true for every i from 1 to N−1.

(Note: Given a string str, stri denotes the ascii value of the ith character (0-indexed) of str. |x| denotes the absolute value of an integer x)

SAMPLE INPUT
2
acxz
bcxz

SAMPLE OUTPUT
Funny
Not Funny

Explanation

Consider the 1st testcase acxz :

c-a
=
x-z
= 2

z-x
=
a-c
= 2

Consider the 2st testcase bcxz

|c-b| != |x-z|

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today the North Pole hosts an Olympiad in a sport called... toy igloo skyscrapers' building!

There are n walruses taking part in the contest. Each walrus is given a unique number from 1 to n. After start each walrus begins to build his own igloo skyscraper. Initially, at the moment of time equal to 0, the height of the skyscraper i-th walrus is equal to ai. Each minute the i-th walrus finishes building bi floors.

The journalists that are reporting from the spot where the Olympiad is taking place, make q queries to the organizers. Each query is characterized by a group of three numbers li, ri, ti. The organizers respond to each query with a number x, such that:

1. Number x lies on the interval from li to ri inclusive (li ≤ x ≤ ri).

2. The skyscraper of the walrus number x possesses the maximum height among the skyscrapers of all walruses from the interval [li, ri] at the moment of time ti.

For each journalists' query print the number of the walrus x that meets the above-given criteria. If there are several possible answers, print any of them.

Input

The first line contains numbers n and q (1 ≤ n, q ≤ 105). Next n lines contain pairs of numbers ai, bi (1 ≤ ai, bi ≤ 109). Then follow q queries i the following format li, ri, ti, one per each line (1 ≤ li ≤ ri ≤ n, 0 ≤ ti ≤ 106). All input numbers are integers.

Output

For each journalists' query print the number of the walrus x that meets the criteria, given in the statement. Print one number per line.

Examples

Input

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


Output

5
2
1
5


Input

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


Output

3
3
3
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's use decorators to build a name directory! You are given some information about $N$ people. Each person has a first name, last name, age and sex. Print their names in a specific format sorted by their age in ascending order i.e. the youngest person's name should be printed first. For two people of the same age, print them in the order of their input.

For Henry Davids, the output should be: 

Mr. Henry Davids

For Mary George, the output should be:

Ms. Mary George

Input Format

The first line contains the integer $N$, the number of people.

$N$ lines follow each containing the space separated values of the first name, last name, age and sex, respectively.  

Constraints 

$1\leq N\leq10$

Output Format

Output $N$ names on separate lines in the format described above in ascending order of age. 

Sample Input

3
Mike Thomson 20 M
Robert Bustle 32 M
Andria Bustle 30 F

Sample Output

Mr. Mike Thomson
Ms. Andria Bustle
Mr. Robert Bustle

Concept

For sorting a nested list based on some parameter, you can use the itemgetter library. You can read more about it here.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of integers arr, you are initially positioned at the first index of the array.
In one step you can jump from index i to index:

i + 1 where: i + 1 < arr.length.
i - 1 where: i - 1 >= 0.
j where: arr[i] == arr[j] and i != j.

Return the minimum number of steps to reach the last index of the array.
Notice that you can not jump outside of the array at any time.
 
Example 1:
Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

Example 2:
Input: arr = [7]
Output: 0
Explanation: Start index is the last index. You don't need to jump.

Example 3:
Input: arr = [7,6,9,6,9,6,9,7]
Output: 1
Explanation: You can jump directly from index 0 to index 7 which is last index of the array.

Example 4:
Input: arr = [6,1,9]
Output: 2

Example 5:
Input: arr = [11,22,7,7,7,7,7,7,7,22,13]
Output: 3

 
Constraints:

1 <= arr.length <= 5 * 10^4
-10^8 <= arr[i] <= 10^8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The First Universal Bank of Denview has just been robbed! You want to catch the robbers before they leave the state.

The state of Calirado can be represented by a rectangular $n$-by-$m$ grid of characters, with the character in each grid cell denoting a terrain type. The robbers begin within the cell marked ‘B’, indicating the Bank of Denview. They will then travel across the state by moving from grid cell to grid cell in the four cardinal directions (left, right, up, down). (Note that the robbers pass only through grid edges, and not corners.) If the robbers manage to leave the state (by crossing any boundary edge of the grid) they will go into hiding, never to be seen again. You must stop this.

To catch the robbers, you can set up barricades. Barricades are placed inside a grid cell, and prevent the robbers from traveling into the cell (from any direction). Each grid square consists of a different type of terrain, with different cost for placing a barricade. You cannot place a barricade on the bank (‘B’) or on any cell containing a dot (‘.’), though the robbers can travel freely through these cells. Every other cell will contain a lowercase English letter, indicating a terrain type.

Find the cheapest way to prevent the robbers from escaping Calirado.

-----Input-----
The first line contains three integers $n$, $m$, and $c$ ($1 \le n, m \le 30$, $1 \le c \le 26$): the dimensions of the grid representing Calirado, and the number of different terrain types. Then follows $m$ lines of exactly $n$ characters each: the map of Calirado. Each character is either ‘B’, ‘.’, or one of the first $c$ lowercase letters of the English alphabet. Calirado is guaranteed to contain exactly one bank. After the grid, there is a line containing $c$ space-separated integers $1 \leq c_ i \leq 100000$, the costs of placing a barricade on a grid cell of each terrain type. $c_1$ is the cost for terrain type ‘a’, $c_2$ is the cost for ‘b’, and so forth.

-----Output-----
Print one integer, the minimum total cost of the barricades that you need to place to prevent the robbers from escaping. If there is no way to prevent the robbers from escaping, print -1 instead.

In the first example, the minimum cost is to barricade the central three squares on each side of the bank for a total cost of $12$.

In the second example, since the bank is on the border, there is no way to prevent the robbers from escaping the state.

In the third example, we must prevent the robbers from leaving the bank to the top, bottom, and right, or else we cannot prevent them from leaving the state. To the left, however, it is cheaper to allow passage through the ‘b’ cell, and then barricade in each of the three directions from there. The total cost is $7 + 5 + 7 + 3(1) = 22$.

-----Examples-----
Sample Input 1:
5 5 1
aaaaa
a...a
a.B.a
a...a
aaaaa
1
Sample Output 1:
12

Sample Input 2:
2 2 1
aB
aa
1
Sample Output 2:
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. You are given two strings; calculate the distance between them.

Input

The input consists of two lines. Each line contains a string of characters 'A'-'Z' between 1 and 100 characters, inclusive. The strings have equal length.

Output

Output Hamming distance between the strings.

Examples

Input

CODECHEF
TOPCODER


Output

6


Input

HAMMING
DISTANC


Output

6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A n x m grid consists of 'n' rows and 'm' columns. You are given 'n' elements, where each ni denotes the sum of elements of the ith row of the grid. You are also given 'm' elements, where each mi denotes the sum of elements of the ith column of the grid. You need to construct the grid by filling the desired cells with values in the range [1, 5] inclusive such that when elements arranged row-wise (a11, a12, a21, a22) represent the lexicographically shortest solution of the grid. Here aij represents the element at ith row and jth column.

Explanation:

Let there be two possible solutions for these row and column sums:

|a1 a2|                               

|a3 a4|

and

|b1 b2|

|b3 b4|

(a1, a2, a3, a4) is lexicographically smaller than (b1, b2, b3, b4) if first index 'i' where ai and bi differs, ai < bi satisfies.

Input:

There are 't' test cases. For each test case you will be given 'n' - number of rows and 'm' - number of columns. This is followed by a line containing 'n' space separated integers 'ni', sum of elements of the ith row. Next line contains 'm' space separated integers 'mi', sum of elements of the ith column.

Output:

You need to print the lexicographically shortest grid solution. There always exists a solution. This needs to be printed in 'n' lines, each line containing 'm' space separated elements of the 'ni' row.

As for a 2 x 2 grid print :

a11 a12

a21 a22

Constraints:

t ≤ 50

1 ≤ m,n ≤ 40

Each element of grid will be [1,5]

SAMPLE INPUT
1
3 3
6 10 6
6 9 7

SAMPLE OUTPUT
1 1 4 
3 5 2 
2 3 1

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