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

Circles Island is known for its mysterious shape: it is a completely flat island with its shape being a union of circles whose centers are on the $x$-axis and their inside regions.

The King of Circles Island plans to build a large square on Circles Island in order to celebrate the fiftieth anniversary of his accession. The King wants to make the square as large as possible. The whole area of the square must be on the surface of Circles Island, but any area of Circles Island can be used for the square. He also requires that the shape of the square is square (of course!) and at least one side of the square is parallel to the $x$-axis.

You, a minister of Circles Island, are now ordered to build the square. First, the King wants to know how large the square can be. You are given the positions and radii of the circles that constitute Circles Island. Answer the side length of the largest possible square.

$N$ circles are given in an ascending order of their centers' $x$-coordinates. You can assume that for all $i$ ($1 \le i \le N-1$), the $i$-th and $(i+1)$-st circles overlap each other. You can also assume that no circles are completely overlapped by other circles.

<image>

[fig.1 : Shape of Circles Island and one of the largest possible squares for test case #1 of sample input]

Input

The input consists of multiple datasets. The number of datasets does not exceed $30$. Each dataset is formatted as follows.

> $N$
> $X_1$ $R_1$
> :
> :
> $X_N$ $R_N$

The first line of a dataset contains a single integer $N$ ($1 \le N \le 50{,}000$), the number of circles that constitute Circles Island. Each of the following $N$ lines describes a circle. The $(i+1)$-st line contains two integers $X_i$ ($-100{,}000 \le X_i \le 100{,}000$) and $R_i$ ($1 \le R_i \le 100{,}000$). $X_i$ denotes the $x$-coordinate of the center of the $i$-th circle and $R_i$ denotes the radius of the $i$-th circle. The $y$-coordinate of every circle is $0$, that is, the center of the $i$-th circle is at ($X_i$, $0$).

You can assume the followings.

* For all $i$ ($1 \le i \le N-1$), $X_i$ is strictly less than $X_{i+1}$.
* For all $i$ ($1 \le i \le N-1$), the $i$-th circle and the $(i+1)$-st circle have at least one common point ($X_{i+1} - X_i \le R_i + R_{i+1}$).
* Every circle has at least one point that is not inside or on the boundary of any other circles.



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

Output

For each dataset, output a line containing the side length of the square with the largest area. The output must have an absolute or relative error at most $10^{-4}$.

Sample Input


2
0 8
10 8
2
0 7
10 7
0

Output for the Sample Input


12.489995996796796
9.899494936611665





Example

Input

2
0 8
10 8
2
0 7
10 7
0


Output

12.489995996796796
9.899494936611665

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp knows that if the sum of the digits of a number is divisible by $3$, then the number itself is divisible by $3$. He assumes that the numbers, the sum of the digits of which is divisible by $4$, are also somewhat interesting. Thus, he considers a positive integer $n$ interesting if its sum of digits is divisible by $4$.

Help Polycarp find the nearest larger or equal interesting number for the given number $a$. That is, find the interesting number $n$ such that $n \ge a$ and $n$ is minimal.


-----Input-----

The only line in the input contains an integer $a$ ($1 \le a \le 1000$).


-----Output-----

Print the nearest greater or equal interesting number for the given number $a$. In other words, print the interesting number $n$ such that $n \ge a$ and $n$ is minimal.


-----Examples-----
Input
432

Output
435

Input
99

Output
103

Input
237

Output
237

Input
42

Output
44

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer N, You need to find the Nth smallest number which only contains odd digits i.e. 1,3,5,7,9 means no even digits are allowed on that number (12 will not consider). For example, the starting numbers which only contain odd digits are 1,3,5,7,9,11,13,15,17,19,31,33,35 and so on.
Example 1:
Input:
N=3
Output:
5
Explanation:
First three numbers are 1, 3, 5.
Here 5 is the 3rd number, where contains
only odd digits.
Example 2:
Input:
N=13
Output:
35
Explanation:
First 13 numbers are 1,3,5,7,9,
11,13,15,17,19,31,33,35, here 35 
is the answer.
Your Task:
You don't need to read input or print anything. Your task is to complete the function findNumber() which takes a single variable N and returns the smallest Nth number which only contains odd digits.
Expected Time Complexity: O(logN)
Expected Space Complexity: O(1)
Constraints:
1 <= N <= 10^12

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vus the Cossack has two binary strings, that is, strings that consist only of "0" and "1". We call these strings $a$ and $b$. It is known that $|b| \leq |a|$, that is, the length of $b$ is at most the length of $a$.

The Cossack considers every substring of length $|b|$ in string $a$. Let's call this substring $c$. He matches the corresponding characters in $b$ and $c$, after which he counts the number of positions where the two strings are different. We call this function $f(b, c)$.

For example, let $b = 00110$, and $c = 11000$. In these strings, the first, second, third and fourth positions are different.

Vus the Cossack counts the number of such substrings $c$ such that $f(b, c)$ is even.

For example, let $a = 01100010$ and $b = 00110$. $a$ has four substrings of the length $|b|$: $01100$, $11000$, $10001$, $00010$.  $f(00110, 01100) = 2$; $f(00110, 11000) = 4$; $f(00110, 10001) = 4$; $f(00110, 00010) = 1$. 

Since in three substrings, $f(b, c)$ is even, the answer is $3$.

Vus can not find the answer for big strings. That is why he is asking you to help him.


-----Input-----

The first line contains a binary string $a$ ($1 \leq |a| \leq 10^6$) — the first string.

The second line contains a binary string $b$ ($1 \leq |b| \leq |a|$) — the second string.


-----Output-----

Print one number — the answer.


-----Examples-----
Input
01100010
00110

Output
3

Input
1010111110
0110

Output
4



-----Note-----

The first example is explained in the legend.

In the second example, there are five substrings that satisfy us: $1010$, $0101$, $1111$, $1111$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are developing a robot that processes strings. When the robot is given a string t consisting of lowercase English letters, it processes the string by following the procedure below:

1. Let i be the smallest index such that t_i = t_{i + 1}. If such an index does not exist, terminate the procedure.
2. If t_i is `z`, remove t_i and t_{i + 1} from t. Otherwise, let c be the next letter of t_i in the English alphabet, and replace t_i and t_{i + 1} together with c, reducing the length of t by 1.
3. Go back to step 1.



For example, when the robot is given the string `axxxxza`, it will be processed as follows: `axxxxza` → `ayxxza` → `ayyza` → `azza` → `aa` → `b`.

You are given a string s consisting of lowercase English letters. Answer Q queries. The i-th query is as follows:

* Assume that the robot is given a substring of s that runs from the l_i-th character and up to the r_i-th character (inclusive). Will the string be empty after processing?

Constraints

* 1 ≤ |s| ≤ 5 × 10^5
* s consists of lowercase English letters.
* 1 ≤ Q ≤ 10^5
* 1 ≤ l_i ≤ r_i ≤ |s|

Input

The input is given from Standard Input in the following format:


s
Q
l_1 r_1
l_2 r_2
:
l_Q r_Q


Output

Print Q lines. The i-th line should contain the answer to the i-th query: `Yes` or `No`.

Examples

Input

axxxxza
2
1 7
2 6


Output

No
Yes


Input

aabcdefghijklmnopqrstuvwxyz
1
1 27


Output

Yes


Input

yzyyyzyzyyyz
8
1 6
7 12
1 12
6 11
1 1
1 3
4 9
3 8


Output

Yes
Yes
Yes
Yes
No
No
No
No

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of integers, return the smallest common factors of all integers in the array.

When i say **Smallest Common Factor** i mean the smallest number above 1 that can divide all numbers in the array without a remainder.

If there are no common factors above 1, return 1 (technically 1 is always a common factor).

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Those days, many boys use beautiful girls' photos as avatars in forums. So it is pretty hard to tell the gender of a user at the first glance. Last year, our hero went to a forum and had a nice chat with a beauty (he thought so). After that they talked very often and eventually they became a couple in the network. 

But yesterday, he came to see "her" in the real world and found out "she" is actually a very strong man! Our hero is very sad and he is too tired to love again now. So he came up with a way to recognize users' genders by their user names.

This is his method: if the number of distinct characters in one's user name is odd, then he is a male, otherwise she is a female. You are given the string that denotes the user name, please help our hero to determine the gender of this user by his method.

Input Specification:
The first line contains a non-empty string, that contains only lowercase English letters — the user name. This string contains at most 100 letters.

Output Specification:
If it is a female by our hero's method, print "CHAT WITH HER!" (without the quotes), otherwise, print "IGNORE HIM!" (without the quotes).

Demo Input:
['wjmzbmr\n', 'xiaodao\n', 'sevenkplus\n']

Demo Output:
['CHAT WITH HER!\n', 'IGNORE HIM!\n', 'CHAT WITH HER!\n']

Note:
For the first example. There are 6 distinct characters in "wjmzbmr". These characters are: "w", "j", "m", "z", "b", "r". So wjmzbmr is a female and you should print "CHAT WITH HER!".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Luka is fooling around in chemistry class again! Instead of balancing equations he is writing coded sentences on a piece of paper. Luka modifies every word in a sentence by adding, after each vowel (letters ’a’, ’e’, ’i’, ’o’ and ’u’), the letter ’p’ and then that same vowel again. For example, the word “kemija” becomes “kepemipijapa” and the word “paprika” becomes “papapripikapa”. The teacher took Luka’s paper with the coded sentences and wants to decode them.

Write a program that decodes Luka’s sentence.

-----Input-----
The coded sentence will be given on a single line. The sentence consists only of lowercase letters of the English alphabet and spaces. The words will be separated by exactly one space and there will be no leading or trailing spaces. The total number of character will be at most 100.

-----Output-----
Output the decoded sentence on a single line.

-----Examples-----
Sample Input:
zepelepenapa papapripikapa
Sample Output:
zelena paprika

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Harry Potter and He-Who-Must-Not-Be-Named engaged in a fight to the death once again. This time they are located at opposite ends of the corridor of length l. Two opponents simultaneously charge a deadly spell in the enemy. We know that the impulse of Harry's magic spell flies at a speed of p meters per second, and the impulse of You-Know-Who's magic spell flies at a speed of q meters per second.

The impulses are moving through the corridor toward each other, and at the time of the collision they turn round and fly back to those who cast them without changing their original speeds. Then, as soon as the impulse gets back to it's caster, the wizard reflects it and sends again towards the enemy, without changing the original speed of the impulse.

Since Harry has perfectly mastered the basics of magic, he knows that after the second collision both impulses will disappear, and a powerful explosion will occur exactly in the place of their collision. However, the young wizard isn't good at math, so he asks you to calculate the distance from his position to the place of the second meeting of the spell impulses, provided that the opponents do not change positions during the whole fight.


-----Input-----

The first line of the input contains a single integer l (1 ≤ l ≤ 1 000) — the length of the corridor where the fight takes place.

The second line contains integer p, the third line contains integer q (1 ≤ p, q ≤ 500) — the speeds of magical impulses for Harry Potter and He-Who-Must-Not-Be-Named, respectively.


-----Output-----

Print a single real number — the distance from the end of the corridor, where Harry is located, to the place of the second meeting of the spell impulses. Your answer will be considered correct if its absolute or relative error will not exceed 10^{ - 4}. 

Namely: let's assume that your answer equals a, and the answer of the jury is b. The checker program will consider your answer correct if $\frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-4}$.


-----Examples-----
Input
100
50
50

Output
50

Input
199
60
40

Output
119.4



-----Note-----

In the first sample the speeds of the impulses are equal, so both of their meetings occur exactly in the middle of the corridor.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Valera the horse lives on a plane. The Cartesian coordinate system is defined on this plane. Also an infinite spiral is painted on the plane. The spiral consists of segments: [(0,<=0),<=(1,<=0)], [(1,<=0),<=(1,<=1)], [(1,<=1),<=(<=-<=1,<=1)], [(<=-<=1,<=1),<=(<=-<=1,<=<=-<=1)], [(<=-<=1,<=<=-<=1),<=(2,<=<=-<=1)], [(2,<=<=-<=1),<=(2,<=2)] and so on. Thus, this infinite spiral passes through each integer point of the plane.

Valera the horse lives on the plane at coordinates (0,<=0). He wants to walk along the spiral to point (*x*,<=*y*). Valera the horse has four legs, so he finds turning very difficult. Count how many times he will have to turn if he goes along a spiral from point (0,<=0) to point (*x*,<=*y*).

Input Specification:
The first line contains two space-separated integers *x* and *y* (|*x*|,<=|*y*|<=≤<=100).

Output Specification:
Print a single integer, showing how many times Valera has to turn.

Demo Input:
['0 0\n', '1 0\n', '0 1\n', '-1 -1\n']

Demo Output:
['0\n', '0\n', '2\n', '3\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In ordinary chess, the pieces are only of two colors, black and white. In our version of chess, we are including new pieces with unique movements. One of the most powerful pieces in this version is the red knight.  

The red knight can move to six different positions based on its current position (UpperLeft, UpperRight, Right, LowerRight, LowerLeft, Left) as shown in the figure below. 

The board is a grid of size $n\times n$. Each cell is identified with a pair of coordinates $(i,j)$, where $\boldsymbol{i}$ is the row number and $j$ is the column number, both zero-indexed. Thus, $(0,0)$ is the upper-left corner and $(n-1,n-1)$ is the bottom-right corner. 

Complete the function printShortestPath, which takes as input the grid size $n$, and the coordinates of the starting and ending position $(i_{start},j_{start})$ and $(i_{end},j_{end})$ respectively, as input. The function does not return anything.     

Given the coordinates of the starting position of the red knight and the coordinates of the destination, print the minimum number of moves that the red knight has to make in order to reach the destination and after that, print the order of the moves that must be followed to reach the destination in the shortest way. If the destination cannot be reached, print only the word "Impossible". 

Note: There may be multiple shortest paths leading to the destination. Hence, assume that the red knight considers its possible neighbor locations in the following order of priority: UL, UR, R, LR, LL, L. In other words, if there are multiple possible options, the red knight prioritizes the first move in this list, as long as the shortest path is still achievable. Check sample input $2$ for an illustration.

Input Format

The first line of input contains a single integer $n$. The second line contains four space-separated integers $i_{start},j_{start},i_{end},j_{end}$. $(i_{start},j_{start})$ denotes the coordinates of the starting position and $(i_{end},j_{end})$ denotes the coordinates of the final position.

Constraints

$5\leq n\leq200$  
$0\leq i_{start},j_{start},i_{end},j_{end}<n$  
the starting and the ending positions are different

Output Format

If the destination can be reached, print two lines. In the first line, print a single integer denoting the minimum number of moves that the red knight has to make in order to reach the destination. In the second line, print the space-separated sequence of moves. 

If the destination cannot be reached, print a single line containing only the word Impossible.

Sample Input 0
7
6 6 0 1

Sample Output 0
4
UL UL UL L

Explanation 0

Sample Input 1
6
5 1 0 5

Sample Output 1
Impossible

Explanation 1

Sample Input 2
7
0 3 4 3

Sample Output 2
2
LR LL

Explanation 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Mr. Kitayuta's Gift

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Mr. Kitayuta has kindly given you a string *s* consisting of lowercase English letters. You are asked to insert exactly one lowercase English letter into *s* to make it a palindrome. A palindrome is a string that reads the same forward and backward. For example, "noon", "testset" and "a" are all palindromes, while "test" and "kitayuta" are not.

You can choose any lowercase English letter, and insert it to any position of *s*, possibly to the beginning or the end of *s*. You have to insert a letter even if the given string is already a palindrome.

If it is possible to insert one lowercase English letter into *s* so that the resulting string will be a palindrome, print the string after the insertion. Otherwise, print "NA" (without quotes, case-sensitive). In case there is more than one palindrome that can be obtained, you are allowed to print any of them.

Input Specification:
The only line of the input contains a string *s* (1<=≤<=|*s*|<=≤<=10). Each character in *s* is a lowercase English letter.

Output Specification:
If it is possible to turn *s* into a palindrome by inserting one lowercase English letter, print the resulting string in a single line. Otherwise, print "NA" (without quotes, case-sensitive). In case there is more than one solution, any of them will be accepted.

Demo Input:
['revive\n', 'ee\n', 'kitayuta\n']

Demo Output:
['reviver\n', 'eye', 'NA\n']

Note:
For the first sample, insert 'r' to the end of "revive" to obtain a palindrome "reviver".

For the second sample, there is more than one solution. For example, "eve" will also be accepted.

For the third sample, it is not possible to turn "kitayuta" into a palindrome by just inserting one letter.

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

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:


Input: haystack = "hello", needle = "ll"
Output: 2


Example 2:


Input: haystack = "aaaaa", needle = "bba"
Output: -1


Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Array inversion indicates how far the array is from being sorted.

Inversions are pairs of elements in array that are out of order.

## Examples

```
[1, 2, 3, 4]  =>  0 inversions
[1, 3, 2, 4]  =>  1 inversion: 2 and 3
[4, 1, 2, 3]  =>  3 inversions: 4 and 1, 4 and 2, 4 and 3
[4, 3, 2, 1]  =>  6 inversions: 4 and 3, 4 and 2, 4 and 1, 3 and 2, 3 and 1, 2 and 1
```

## Goal

The goal is to come up with a function that can calculate inversions for any arbitrary array

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array $a$ consisting of $n$ integers.

Your task is to determine if $a$ has some subsequence of length at least $3$ that is a palindrome.

Recall that an array $b$ is called a subsequence of the array $a$ if $b$ can be obtained by removing some (possibly, zero) elements from $a$ (not necessarily consecutive) without changing the order of remaining elements. For example, $[2]$, $[1, 2, 1, 3]$ and $[2, 3]$ are subsequences of $[1, 2, 1, 3]$, but $[1, 1, 2]$ and $[4]$ are not.

Also, recall that a palindrome is an array that reads the same backward as forward. In other words, the array $a$ of length $n$ is the palindrome if $a_i = a_{n - i - 1}$ for all $i$ from $1$ to $n$. For example, arrays $[1234]$, $[1, 2, 1]$, $[1, 3, 2, 2, 3, 1]$ and $[10, 100, 10]$ are palindromes, but arrays $[1, 2]$ and $[1, 2, 3, 1]$ are not.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 100$) — the number of test cases.

Next $2t$ lines describe test cases. The first line of the test case contains one integer $n$ ($3 \le n \le 5000$) — the length of $a$. The second line of the test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), where $a_i$ is the $i$-th element of $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$ ($\sum n \le 5000$).


-----Output-----

For each test case, print the answer — "YES" (without quotes) if $a$ has some subsequence of length at least $3$ that is a palindrome and "NO" otherwise.


-----Example-----
Input
5
3
1 2 1
5
1 2 2 3 2
3
1 1 2
4
1 2 2 1
10
1 1 2 2 3 3 4 4 5 5

Output
YES
YES
NO
YES
NO



-----Note-----

In the first test case of the example, the array $a$ has a subsequence $[1, 2, 1]$ which is a palindrome.

In the second test case of the example, the array $a$ has two subsequences of length $3$ which are palindromes: $[2, 3, 2]$ and $[2, 2, 2]$.

In the third test case of the example, the array $a$ has no subsequences of length at least $3$ which are palindromes.

In the fourth test case of the example, the array $a$ has one subsequence of length $4$ which is a palindrome: $[1, 2, 2, 1]$ (and has two subsequences of length $3$ which are palindromes: both are $[1, 2, 1]$).

In the fifth test case of the example, the array $a$ has no subsequences of length at least $3$ which are palindromes.

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