vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given an integer N. Consider an infinite N-ary tree as shown below:

<image>

Figure: an infinite N-ary tree for the case N = 3

As shown in the figure, each vertex is indexed with a unique positive integer, and for every positive integer there is a vertex indexed with it. The root of the tree has the index 1. For the remaining vertices, vertices in the upper row have smaller indices than those in the lower row. Among the vertices in the same row, a vertex that is more to the left has a smaller index.

Regarding this tree, process Q queries. The i-th query is as follows:

* Find the index of the lowest common ancestor (see Notes) of Vertex v_i and w_i.

Constraints

* 1 ≤ N ≤ 10^9
* 1 ≤ Q ≤ 10^5
* 1 ≤ v_i < w_i ≤ 10^9

Input

Input is given from Standard Input in the following format:


N Q
v_1 w_1
:
v_Q w_Q


Output

Print Q lines. The i-th line (1 ≤ i ≤ Q) must contain the index of the lowest common ancestor of Vertex v_i and w_i.

Examples

Input

3 3
5 7
8 11
3 9


Output

2
1
3


Input

100000 2
1 2
3 4


Output

1
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An angel lives in the clouds above the city where Natsume lives. The angel, like Natsume, loves cats and often comes down to the ground to play with cats. To get down to the ground, the angel made a long, long staircase leading from the clouds to the ground. However, the angel thought that it would be boring to just go down every time, so he worked on the stairs so that he could make a sound when he stepped on the steps. Use this to get off while playing music.

Music is played using 12 kinds of sounds. This time, I will ignore the octave of the sound and consider only 12 types of C, C #, D, D #, E, F, F #, G, G #, A, A #, B. The difference between adjacent sounds is called a semitone. For example, raising C by a semitone gives C #, and raising C # by a semitone gives D. Conversely, lowering G by a semitone gives F #, and lowering F # by a semitone gives F. Note that raising E by a semitone results in F, and raising B by a semitone results in C.

The mechanism of sound output from the stairs is as follows. First, the stairs consist of n white boards floating in the air. One of the 12 tones is assigned to each of the 1st to nth boards counting from the clouds. Let's write this as Ti (i = 1 ... n). Also, for the sake of simplicity, consider the clouds as the 0th stage and the ground as the n + 1th stage (however, no scale is assigned to them). When the angel is in the k (k = 0 ... n) stage, the next step is to go to any of the k-1, k + 1, k + 2 stages that exist. However, it cannot move after descending to the n + 1th stage (ground), and cannot return to it after leaving the 0th stage (cloud). Each movement makes a sound according to the following rules.

I got down to the k + 1 stage
The sound of Tk + 1 sounds.
k + 2nd step
A semitone up of Tk + 2 sounds.
I returned to the k-1 stage
A semitone lower Tk-1 sounds.

Information on the stairs T1 ... Tn and the song S1 ... Sm that the angel wants to play are given. At this time, another sound must not be played before, during, or after the song you want to play. Determine if the angel can play this song and descend from the clouds to the ground.

Notes on Submission

Multiple datasets are given in the above format. The first line of input data gives the number of datasets. Create a program that outputs the output for each data set in order in the above format.



Input

The first line of input gives the number of steps n of the stairs and the length m of the song that the angel wants to play. The second line is the information of the stairs, and T1, T2, ..., Tn are given in this order. The third line is the song that the angel wants to play, and S1, S2, ..., Sm are given in this order. All of these are separated by a single space character and satisfy 1 <= n, m <= 50000.

Output

Output "Yes" if the angel can get down to the ground while playing the given song, otherwise output "No" on one line.

Example

Input

4
6 4
C E D# F G A
C E F G
6 4
C E D# F G A
C D# F G
3 6
C D D
D# B D B D# C#
8 8
C B B B B B F F
C B B B B B B B


Output

Yes
No
Yes
No

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Wallace the Weightlifting Walrus is training for a contest where it will have to lift $1000$ kg. Wallace has some weight plates lying around, possibly of different weights, and its goal is to add some of the plates to a bar so that it can train with a weight as close as possible to $1000$ kg.

In case there exist two such numbers which are equally close to $1000$ (e.g. $998$ and $1002$), Wallace will pick the greater one (in this case $1002$).

Help Wallace the Weightlifting Walrus and tell it which weight it will have to lift.

-----Input-----
The first line of the input contains the number of plates $n$ ($1 \leq n \leq 1000$). Each of the following $n$ lines contains one positive integer less than or equal to $1000$, denoting the weight of each plate.

-----Output-----
Output one integer, the combined weight closest to $1000$.

-----Examples-----
Sample Input:
4
900
500
498
4
Sample Output:
1002

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The defaultdict tool is a container in the collections class of Python. It's similar to the usual dictionary (dict) container, but the only difference is that a defaultdict will have a default value if that key has not been set yet. If you didn't use a defaultdict you'd have to check to see if that key exists, and if it doesn't, set it to what you want. 

For example:

from collections import defaultdict
d = defaultdict(list)
d['python'].append("awesome")
d['something-else'].append("not relevant")
d['python'].append("language")
for i in d.items():
    print i

This prints:

('python', ['awesome', 'language'])
('something-else', ['not relevant'])

In this challenge, you will be given $2$ integers, $n$ and $m$. There are $n$ words, which might repeat, in word group $\mbox{A}$. There are $m$ words belonging to word group $\mbox{B}$. For each  $m$ words, check whether the word has appeared in group $\mbox{A}$ or not. Print the indices of each occurrence of $m$ in group $\mbox{A}$. If it does not appear, print $-1$.

Example  

Group A contains 'a', 'b', 'a'
Group B contains 'a', 'c'

For the first word in group B, 'a', it appears at positions $\mbox{I}$ and $3$ in group A.
The second word, 'c', does not appear in group A, so print $-1$.

Expected output:

1 3
-1

Input Format

The first line contains integers, $n$ and $m$ separated by a space. 

The next $n$ lines contains the words belonging to group $\mbox{A}$. 

The next $m$ lines contains the words belonging to group $\mbox{B}$.

Constraints

$1\leq n\leq10000$ 

$1\leq m\leq100$ 

$1\leq\textit{length of each word in the input}\leq100$

Output Format

Output $m$ lines. 

The $i^{\mbox{th}}$ line should contain the $\mbox{I}$-indexed positions of the occurrences of the $i^{\mbox{th}}$ word separated by spaces. 

Sample Input
STDIN   Function
-----   --------
5 2     group A size n = 5, group B size m = 2
a       group A contains 'a', 'a', 'b', 'a', 'b'
a
b
a
b
a       group B contains 'a', 'b'
b

Sample Output
1 2 4
3 5

Explanation

'a' appeared $3$ times in positions $\mbox{I}$, $2$ and $\begin{array}{c}A\end{array}$. 

 'b' appeared $2$ times in positions $3$ and $5$. 

In the sample problem, if 'c' also appeared in word group $\mbox{B}$, you would print $-1$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Sereja has got an array, consisting of *n* integers, *a*1,<=*a*2,<=...,<=*a**n*. Sereja is an active boy, so he is now going to complete *m* operations. Each operation will have one of the three forms:
 1.  Make *v**i*-th array element equal to *x**i*. In other words, perform the assignment *a**v**i*<==<=*x**i*. 1.  Increase each array element by *y**i*. In other words, perform *n* assignments *a**i*<==<=*a**i*<=+<=*y**i* (1<=≤<=*i*<=≤<=*n*). 1.  Take a piece of paper and write out the *q**i*-th array element. That is, the element *a**q**i*. 
Help Sereja, complete all his operations.

Input Specification:
The first line contains integers *n*, *m* (1<=≤<=*n*,<=*m*<=≤<=105). The second line contains *n* space-separated integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=109) — the original array.

Next *m* lines describe operations, the *i*-th line describes the *i*-th operation. The first number in the *i*-th line is integer *t**i* (1<=≤<=*t**i*<=≤<=3) that represents the operation type. If *t**i*<==<=1, then it is followed by two integers *v**i* and *x**i*, (1<=≤<=*v**i*<=≤<=*n*,<=1<=≤<=*x**i*<=≤<=109). If *t**i*<==<=2, then it is followed by integer *y**i* (1<=≤<=*y**i*<=≤<=104). And if *t**i*<==<=3, then it is followed by integer *q**i* (1<=≤<=*q**i*<=≤<=*n*).

Output Specification:
For each third type operation print value *a**q**i*. Print the values in the order, in which the corresponding queries follow in the input.

Demo Input:
['10 11\n1 2 3 4 5 6 7 8 9 10\n3 2\n3 9\n2 10\n3 1\n3 10\n1 1 10\n2 10\n2 10\n3 1\n3 10\n3 9\n']

Demo Output:
['2\n9\n11\n20\n30\n40\n39\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are many anime that are about "love triangles": Alice loves Bob, and Charlie loves Bob as well, but Alice hates Charlie. You are thinking about an anime which has *n* characters. The characters are labeled from 1 to *n*. Every pair of two characters can either mutually love each other or mutually hate each other (there is no neutral state).

You hate love triangles (A-B are in love and B-C are in love, but A-C hate each other), and you also hate it when nobody is in love. So, considering any three characters, you will be happy if exactly one pair is in love (A and B love each other, and C hates both A and B), or if all three pairs are in love (A loves B, B loves C, C loves A).

You are given a list of *m* known relationships in the anime. You know for sure that certain pairs love each other, and certain pairs hate each other. You're wondering how many ways you can fill in the remaining relationships so you are happy with every triangle. Two ways are considered different if two characters are in love in one way but hate each other in the other. Print this count modulo 1<=000<=000<=007.

Input Specification:
The first line of input will contain two integers *n*,<=*m* (3<=≤<=*n*<=≤<=100<=000, 0<=≤<=*m*<=≤<=100<=000).

The next *m* lines will contain the description of the known relationships. The *i*-th line will contain three integers *a**i*,<=*b**i*,<=*c**i*. If *c**i* is 1, then *a**i* and *b**i* are in love, otherwise, they hate each other (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*, *a**i*<=≠<=*b**i*, ).

Each pair of people will be described no more than once.

Output Specification:
Print a single integer equal to the number of ways to fill in the remaining pairs so that you are happy with every triangle modulo 1<=000<=000<=007.

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

Demo Output:
['4\n', '1\n', '0\n']

Note:
In the first sample, the four ways are to: 
 -  Make everyone love each other -  Make 1 and 2 love each other, and 3 hate 1 and 2 (symmetrically, we get 3 ways from this). 
In the second sample, the only possible solution is to make 1 and 3 love each other and 2 and 4 hate each other.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Bob is preparing to pass IQ test. The most frequent task in this test is to find out which one of the given *n* numbers differs from the others. Bob observed that one number usually differs from the others in evenness. Help Bob — to check his answers, he needs a program that among the given *n* numbers finds one that is different in evenness.

Input Specification:
The first line contains integer *n* (3<=≤<=*n*<=≤<=100) — amount of numbers in the task. The second line contains *n* space-separated natural numbers, not exceeding 100. It is guaranteed, that exactly one of these numbers differs from the others in evenness.

Output Specification:
Output index of number that differs from the others in evenness. Numbers are numbered from 1 in the input order.

Demo Input:
['5\n2 4 7 8 10\n', '4\n1 2 1 1\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Trigrams are a special case of the n-gram, where n is 3. One trigram is a continious sequence of 3 chars in phrase. [Wikipedia](https://en.wikipedia.org/wiki/Trigram)

 - return all trigrams for the given phrase 
 - replace spaces with \_ 
 - return an empty string for phrases shorter than 3

Example:

trigrams('the quick red') ==  the he\_ e\_q \_qu qui uic ick ck\_ k\_r \_re red

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Welcome to Innopolis city. Throughout the whole year, Innopolis citizens suffer from everlasting city construction. 

From the window in your room, you see the sequence of n hills, where i-th of them has height a_{i}. The Innopolis administration wants to build some houses on the hills. However, for the sake of city appearance, a house can be only built on the hill, which is strictly higher than neighbouring hills (if they are present). For example, if the sequence of heights is 5, 4, 6, 2, then houses could be built on hills with heights 5 and 6 only.

The Innopolis administration has an excavator, that can decrease the height of an arbitrary hill by one in one hour. The excavator can only work on one hill at a time. It is allowed to decrease hills up to zero height, or even to negative values. Increasing height of any hill is impossible. The city administration wants to build k houses, so there must be at least k hills that satisfy the condition above. What is the minimum time required to adjust the hills to achieve the administration's plan?

However, the exact value of k is not yet determined, so could you please calculate answers for all k in range $1 \leq k \leq \lceil \frac{n}{2} \rceil$? Here $\lceil \frac{n}{2} \rceil$ denotes n divided by two, rounded up.


-----Input-----

The first line of input contains the only integer n (1 ≤ n ≤ 5000)—the number of the hills in the sequence.

Second line contains n integers a_{i} (1 ≤ a_{i} ≤ 100 000)—the heights of the hills in the sequence.


-----Output-----

Print exactly $\lceil \frac{n}{2} \rceil$ numbers separated by spaces. The i-th printed number should be equal to the minimum number of hours required to level hills so it becomes possible to build i houses.


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

Output
1 2 2 

Input
3
1 2 3

Output
0 2 

Input
5
1 2 3 2 2

Output
0 1 3 



-----Note-----

In the first example, to get at least one hill suitable for construction, one can decrease the second hill by one in one hour, then the sequence of heights becomes 1, 0, 1, 1, 1 and the first hill becomes suitable for construction.

In the first example, to get at least two or at least three suitable hills, one can decrease the second and the fourth hills, then the sequence of heights becomes 1, 0, 1, 0, 1, and hills 1, 3, 5 become suitable for construction.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We say that a string contains the word hackerrank if a subsequence of its characters spell the word hackerrank.  Remeber that a subsequence maintains the order of characters selected from a sequence.   

More formally, let $p[0],p[1],\cdots,p[9]$ be the respective indices of h, a, c, k, e, r, r, a, n, k in string $\boldsymbol{\mathrm{~S~}}$. If $p[0]<p[1]<p[2]<\text{...}<p[9]$ is true, then $\boldsymbol{\mathrm{~S~}}$ contains hackerrank.

For each query, print YES on a new line if the string contains hackerrank, otherwise, print NO.  

Example 

$s=\text{haacckker}\text{rannkk}$  

This contains a subsequence of all of the characters in the proper order.  Answer YES  

$s=\text{haacckkerannk}$  

This is missing the second 'r'.  Answer NO.  

$s=\text{hccaakker}\text{rannkk}$  

There is no 'c' after the first occurrence of an 'a', so answer NO.  

Function Description  

Complete the hackerrankInString function in the editor below.   

hackerrankInString has the following parameter(s):  

string s: a string   

Returns  

string: YES or NO

Input Format

The first line contains an integer $\textit{q}$, the number of queries. 

Each of the next $\textit{q}$ lines contains a single query string $\boldsymbol{\mathrm{~S~}}$.  

Constraints

$2\leq q\leq10^2$  
$10\leq\:\text{length of}\:s\leq10^4$

Sample Input 0
2
hereiamstackerrank
hackerworld

Sample Output 0
YES
NO

Explanation 0

We perform the following $q=2$ queries:

$s=\textbf{hereiamstacker}\textbf{rank}$ 

The characters of hackerrank are bolded in the string above. Because the string contains all the characters in hackerrank in the same exact order as they appear in hackerrank, we return YES.
$s=\textbf{hackerworld}$ does not contain the last three characters of hackerrank, so we return NO.

Sample Input 1
2
hhaacckkekraraannk
rhbaasdndfsdskgbfefdbrsdfhuyatrjtcrtyytktjjt

Sample Output 1
YES
NO



The diagram below depicts our map of Hackerland:

We can cover the entire city by installing $3$ transmitters on houses at locations $\begin{array}{c}4\end{array}$, $\mbox{9}$, and $12$.

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

  $r$ red balls,  $g$ green balls,  $b$ blue balls,  $w$ white balls. 

He allows you to do the following operation as many times as you want: 

  Pick a red ball, a green ball, and a blue ball and then change their color to white. 

You should answer if it's possible to arrange all the balls into a palindrome after several (possibly zero) number of described operations. 


-----Input-----

The first line contains one integer $T$ ($1\le T\le 100$) denoting the number of test cases.

For each of the next $T$ cases, the first line contains four integers $r$, $g$, $b$ and $w$ ($0\le r,g,b,w\le 10^9$).


-----Output-----

For each test case, print "Yes" if it's possible to arrange all the balls into a palindrome after doing several (possibly zero) number of described operations. Otherwise, print "No".


-----Example-----
Input
4
0 1 1 1
8 1 9 3
0 0 0 0
1000000000 1000000000 1000000000 1000000000

Output
No
Yes
Yes
Yes



-----Note-----

In the first test case, you're not able to do any operation and you can never arrange three balls of distinct colors into a palindrome.

In the second test case, after doing one operation, changing $(8,1,9,3)$ to $(7,0,8,6)$, one of those possible palindromes may be "rrrwwwbbbbrbbbbwwwrrr".

A palindrome is a word, phrase, or sequence that reads the same backwards as forwards. For example, "rggbwbggr", "b", "gg" are palindromes while "rgbb", "gbbgr" are not. Notice that an empty word, phrase, or sequence is palindrome.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a train going from Station A to Station B that costs X yen (the currency of Japan).
Also, there is a bus going from Station B to Station C that costs Y yen.
Joisino got a special ticket. With this ticket, she can take the bus for half the fare if she travels from Station A to Station B by train and then travels from Station B to Station C by bus.
How much does it cost to travel from Station A to Station C if she uses this ticket?

-----Constraints-----
 - 1 \leq X,Y \leq 100
 - Y is an even number.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
X Y

-----Output-----
If it costs x yen to travel from Station A to Station C, print x.

-----Sample Input-----
81 58

-----Sample Output-----
110

 - The train fare is 81 yen.
 - The train fare is 58 ⁄ 2=29 yen with the 50% discount.
Thus, it costs 110 yen to travel from Station A to Station C.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Petya sometimes has to water his field. To water the field, Petya needs a tank with exactly V ml of water.

Petya has got N tanks, i-th of them initially containing ai ml of water. The tanks are really large, any of them can contain any amount of water (no matter how large this amount is).

Also Petya has got a scoop that can contain up to K ml of water (initially the scoop is empty). This scoop can be used to get some water from some tank, and after that pour it all into some tank (it is impossible to get water from multiple tanks without pouring it, or leave some water in the scoop when pouring it). When Petya tries to get some water from a tank, he gets min(v, K) water, where v is the current volume of water in the tank.

Is it possible to obtain a tank with exactly V ml of water using these operations? If it is possible, print a sequence of operations that allows to do it. If there are multiple ways to obtain needed amount of water in some tank, print any of them.

Input

The first line contains 3 integers: N (2 ≤ N ≤ 5000), K (1 ≤ K ≤ 5000), and V (0 ≤ V ≤ 109) — the number of tanks, the maximum volume of water the scoop can contain, and the required amount of water in some tank, respectively.

The second line contains N integers ai (0 ≤ ai ≤ 105), where ai is initial volume of water in i-th tank.

Output

If it is impossible to obtain a tank with exactly V ml of water, print NO. 

Otherwise print YES in the first line, and beginning from the second line, print the sequence of operations in the following format: 

Each line has to contain 3 numbers denoting a compressed operation: "cnt x y" (1 ≤ cnt ≤ 109, 1 ≤ x, y ≤ N), where x is the index of the tank where we get water, y is the index of the tank where we pour water, and cnt is the number of times we transfer water from tank x to tank y. 

The number of these lines must not exceed N + 5.

Examples

Input

2 3 5
2 3


Output

YES
1 2 1


Input

2 3 4
2 3


Output

NO


Input

5 2 0
1 3 5 7 9


Output

YES
2 2 1
3 3 1
4 4 1
5 5 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A modified KP number is a positive whole number n with d digits, such that when we split its square into two pieces - a right hand piece r with d digits and a left hand piece l that contains the remaining d or d−1 digits, the sum of the pieces is equal to the original number (i.e. l + r = n).

Note: r may have leading zeros.

Here's an explanation about the ORIGINAL KP Number. A KP number for a given base is a non-negative integer, the representation of whose square in that base can be split into two parts that add up to the original number again. For instance, 45 is a KP number, because 45² = 2025 and 20+25 = 45.

You are given the two positive integers p and q, where p is lower than q. Write a program to determine how many KP numbers are there in the range between p and q (both inclusive) and display them all.

INPUT

There will be two lines of input: p, lowest value q, highest value.

OUTPUT

Output each KP number in the given range, space-separated on a single line. If no KP numbers exist in the given range, print INVALID RANGE.

CONSTRAINTS

0<p<q<100000

SAMPLE INPUT
1
100

SAMPLE OUTPUT
1 9 45 55 99

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