vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Alice and Bob are playing a game. In this game small cubes are placed over each other, forming a cuboid of length B, height L and breadth 1. 
The special property in these cubes is that adjacent cubes always form a cluster. For example,  
 
This denotes are cuboid of L=4, B=5. 'x' denote the small cubes. '.' means empty space.
In this matrix, the rows are numbered 1 to L from bottom to up, and columns are numbered 1 to B from left to right.
Note that a cluster requires a support, otherwise due to gravity it will fall down. Example, this state is not possible:  
Due to gravity, this cluster will settle down, to reach a stable state like this:     
Another example:    
The above configuration will stabilise to:       
So, a cluster not having support will fall down due to gravity. While falling, it would not change it's shape. If any cube in this cluster comes in contact with cube from another cluster or ground, it will stop falling.    

Now the game is as follows:    
Alice and Bob alternate turns, Alice starting first. In each move of his/hers, the player would choose a height and throw an arrow. Alice throws from left to right, and Bob from right to left. If the arrow hits a cube, the cube and arrow both will be destroyed. If due to destruction of a cube, the cuboid becomes unstable, it will stabilise on it's own.         

Example:    
If current state was this,   
If Alice throws an arrow at height 3, the cube at (3,3) will be destroyed, intermediate situation will be this: 
which will settle down to:  
Given the moves of Alice and Bob, can you print the final state of the cuboid.    
Note that, the testdata is such that, at any point of time, no two clusters will be falling at the same time. Also, initially, the cuboid is in the stable state.       

Input: 
First line contains two space separated integers denoting L and B.  
Each of the next L lines contain B characters each.
Each character is either 'x' or '.' , denoting the presence or absence of a cube at that position.   
Next line contains N, the number of moves.   
Next line contains N integers, each integer denoting a height at which the arrow was thrown.

The moves are alternative, first move being made by Alice.       

Output: 
Print the final state of the cuboid.

Constraints:    
1 ≤ L,B ≤ 100
1 ≤ N ≤ 100

SAMPLE INPUT
5 6
......
..xx..
..x...
..xx..
.xxxx.
1
3

SAMPLE OUTPUT
......
......
..xx..
..xx..
.xxxx.

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

Time Limit: 0 seconds

Memory Limit: 256 megabytes

Problem Description:
In a far away kingdom young pages help to set the table for the King. As they are terribly mischievous, one needs to keep an eye on the control whether they have set everything correctly. This time the royal chef Gerasim had the impression that the pages have played a prank again: they had poured the juice from one cup to another. Now Gerasim wants to check his hypothesis. The good thing is that chef Gerasim always pour the same number of milliliters of juice to all cups in the royal kitchen. Having thoroughly measured the juice in each cup, Gerasim asked you to write a program that will determine from which cup juice was poured to which one; otherwise, the program should determine that this time the pages set the table diligently.

To simplify your task we shall consider the cups to be bottomless so that the juice never overfills a cup and pours out, however much it can be. Besides, by some strange reason in a far away kingdom one can only pour to a cup or from one cup to another an integer number of milliliters of juice.

Input Specification:
The first line contains integer *n* — the number of cups on the royal table (1<=≤<=*n*<=≤<=1000). Next *n* lines contain volumes of juice in each cup — non-negative integers, not exceeding 104.

Output Specification:
If the pages didn't pour the juice, print "Exemplary pages." (without the quotes). If you can determine the volume of juice poured during exactly one juice pouring, print "*v* ml. from cup #*a* to cup #*b*." (without the quotes), where *v* represents the volume of poured juice, *a* represents the number of the cup from which the juice was poured (the cups are numbered with consecutive positive integers starting from one in the order in which the cups are described in the input data), *b* represents the number of the cup into which the juice was poured. Finally, if the given juice's volumes cannot be obtained using no more than one pouring (for example, the pages poured the juice from one cup to another more than once or the royal kitchen maids poured the juice into the cups incorrectly), print "Unrecoverable configuration." (without the quotes).

Demo Input:
['5\n270\n250\n250\n230\n250\n', '5\n250\n250\n250\n250\n250\n', '5\n270\n250\n249\n230\n250\n']

Demo Output:
['20 ml. from cup #4 to cup #1.\n', 'Exemplary pages.\n', 'Unrecoverable configuration.\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Berland has managed to repel the flatlanders' attack and is now starting the counter attack.

Flatland has n cities, numbered from 1 to n, and some pairs of them are connected by bidirectional roads. The Flatlandian maps show roads between cities if and only if there is in fact no road between this pair of cities (we do not know whether is it a clever spy-proof strategy or just saving ink). In other words, if two cities are connected by a road on a flatland map, then there is in fact no road between them. The opposite situation is also true: if two cities are not connected by a road on a flatland map, then in fact, there is a road between them.

The berlanders got hold of a flatland map. Now Vasya the Corporal is commissioned by General Touristov to find all such groups of flatland cities, that in each group of cities you can get from any city to any other one, moving along the actual roads. Also the cities from different groups are unreachable from each other, moving along the actual roads. Indeed, destroying such groups one by one is much easier than surrounding all Flatland at once!

Help the corporal complete this task and finally become a sergeant! Don't forget that a flatland map shows a road between cities if and only if there is in fact no road between them. 

Input

The first line contains two space-separated integers n and m (1 ≤ n ≤ 5·105, 0 ≤ m ≤ 106) — the number of cities and the number of roads marked on the flatland map, correspondingly.

Next m lines contain descriptions of the cities on the map. The i-th line contains two integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — the numbers of cities that are connected by the i-th road on the flatland map.

It is guaranteed that each pair of cities occurs in the input no more than once.

Output

On the first line print number k — the number of groups of cities in Flatland, such that in each group you can get from any city to any other one by flatland roads. At the same time, the cities from different groups should be unreachable by flatland roads.

On each of the following k lines first print ti (1 ≤ ti ≤ n) — the number of vertexes in the i-th group. Then print space-separated numbers of cities in the i-th group.

The order of printing groups and the order of printing numbers in the groups does not matter. The total sum ti for all k groups must equal n.

Examples

Input

4 4
1 2
1 3
4 2
4 3


Output

2
2 1 4 
2 2 3 


Input

3 1
1 2


Output

1
3 1 2 3 

Note

In the first sample there are roads only between pairs of cities 1-4 and 2-3.

In the second sample there is no road between cities 1 and 2, but still you can get from one city to the other one through city number 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer $n$. A set, $\mbox{S}$, of triples $(x_i,y_i,z_i)$ is beautiful if and only if:

$0\leq x_i,y_i,z_i$
$x_i+y_i+z_i=n,\forall i:1\leq i\leq|S|$
Let $\mbox{X}$ be the set of different $x_i$'s in $\mbox{S}$, $\mathbf{Y}$ be the set of different $y_i$'s in $\mbox{S}$, and $\mbox{Z}$ be the set of different $z_i$ in $\mbox{S}$. Then $|X|=|Y|=|Z|=|S|$.

The third condition means that all $x_i$'s are pairwise distinct. The same goes for $y_i$ and $z_i$.

Given $n$, find any beautiful set having a maximum number of elements. Then print the cardinality of $\mbox{S}$ (i.e., $\left|S\right|$) on a new line, followed by $\left|S\right|$ lines where each line contains $3$ space-separated integers describing the respective values of $x_i$, $y_i$, and $z_i$.

Input Format

A single integer, $n$.

Constraints

$1\leq n\leq300$  

Output Format

On the first line, print the cardinality of $\mbox{S}$ (i.e., $\left|S\right|$). 

For each of the $\left|S\right|$ subsequent lines, print three space-separated numbers per line describing the respective values of $x_i$, $y_i$, and $z_i$ for triple $\boldsymbol{i}$ in $\mbox{S}$.

Sample Input
3

Sample Output
3
0 1 2
2 0 1
1 2 0

Explanation

In this case, $n=3$. We need to construct a set, $\mbox{S}$, of non-negative integer triples ($x_{i},y_{i},z_{i}$) where $x_{i}+y_{i}+z_{i}=n$. $\mbox{S}$ has the following triples:

$(x_1,y_1,z_1)=(0,1,2)$
$(x_2,y_2,z_2)=(2,0,1)$
$(z_3,y_3,z_3)=(1,2,0)$

We then print the cardinality of this set, $|S|=3$, on a new line, followed by $3$ lines where each line contains three space-separated values describing a triple in $\mbox{S}$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A triple of numbers is said to be poor when two of those numbers are equal but the other number is different from those two numbers.
You will be given three integers A, B, and C. If this triple is poor, print Yes; otherwise, print No.

-----Constraints-----
 - A, B, and C are all integers between 1 and 9 (inclusive).

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

-----Output-----
If the given triple is poor, print Yes; otherwise, print No.

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

-----Sample Output-----
Yes

A and C are equal, but B is different from those two numbers, so this triple is poor.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The semester is already ending, so Danil made an effort and decided to visit a lesson on harmony analysis to know how does the professor look like, at least. Danil was very bored on this lesson until the teacher gave the group a simple task: find 4 vectors in 4-dimensional space, such that every coordinate of every vector is 1 or  - 1 and any two vectors are orthogonal. Just as a reminder, two vectors in n-dimensional space are considered to be orthogonal if and only if their scalar product is equal to zero, that is: $\sum_{i = 1}^{n} a_{i} \cdot b_{i} = 0$.

Danil quickly managed to come up with the solution for this problem and the teacher noticed that the problem can be solved in a more general case for 2^{k} vectors in 2^{k}-dimensinoal space. When Danil came home, he quickly came up with the solution for this problem. Can you cope with it?


-----Input-----

The only line of the input contains a single integer k (0 ≤ k ≤ 9).


-----Output-----

Print 2^{k} lines consisting of 2^{k} characters each. The j-th character of the i-th line must be equal to ' * ' if the j-th coordinate of the i-th vector is equal to  - 1, and must be equal to ' + ' if it's equal to  + 1. It's guaranteed that the answer always exists.

If there are many correct answers, print any.


-----Examples-----
Input
2

Output
++**
+*+*
++++
+**+


-----Note-----

Consider all scalar products in example:  Vectors 1 and 2: ( + 1)·( + 1) + ( + 1)·( - 1) + ( - 1)·( + 1) + ( - 1)·( - 1) = 0  Vectors 1 and 3: ( + 1)·( + 1) + ( + 1)·( + 1) + ( - 1)·( + 1) + ( - 1)·( + 1) = 0  Vectors 1 and 4: ( + 1)·( + 1) + ( + 1)·( - 1) + ( - 1)·( - 1) + ( - 1)·( + 1) = 0  Vectors 2 and 3: ( + 1)·( + 1) + ( - 1)·( + 1) + ( + 1)·( + 1) + ( - 1)·( + 1) = 0  Vectors 2 and 4: ( + 1)·( + 1) + ( - 1)·( - 1) + ( + 1)·( - 1) + ( - 1)·( + 1) = 0  Vectors 3 and 4: ( + 1)·( + 1) + ( + 1)·( - 1) + ( + 1)·( - 1) + ( + 1)·( + 1) = 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ashishgup and FastestFinger play a game. 

They start with a number $n$ and play in turns. In each turn, a player can make any one of the following moves:  Divide $n$ by any of its odd divisors greater than $1$.  Subtract $1$ from $n$ if $n$ is greater than $1$. 

Divisors of a number include the number itself.

The player who is unable to make a move loses the game.

Ashishgup moves first. Determine the winner of the game if both of them play optimally.


-----Input-----

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

The only line of each test case contains a single integer  — $n$ ($1 \leq n \leq 10^9$).


-----Output-----

For each test case, print "Ashishgup" if he wins, and "FastestFinger" otherwise (without quotes).


-----Example-----
Input
7
1
2
3
4
5
6
12

Output
FastestFinger
Ashishgup
Ashishgup
FastestFinger
Ashishgup
FastestFinger
Ashishgup



-----Note-----

In the first test case, $n = 1$, Ashishgup cannot make a move. He loses.

In the second test case, $n = 2$, Ashishgup subtracts $1$ on the first move. Now $n = 1$, FastestFinger cannot make a move, so he loses.

In the third test case, $n = 3$, Ashishgup divides by $3$ on the first move. Now $n = 1$, FastestFinger cannot make a move, so he loses.

In the last test case, $n = 12$, Ashishgup divides it by $3$. Now $n = 4$, FastestFinger is forced to subtract $1$, and Ashishgup gets $3$, so he wins by dividing it by $3$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Levko has an array that consists of integers: *a*1,<=*a*2,<=... ,<=*a**n*. But he doesn’t like this array at all.

Levko thinks that the beauty of the array *a* directly depends on value *c*(*a*), which can be calculated by the formula: 

It’s time to change the world and Levko is going to change his array for the better. To be exact, Levko wants to change the values of at most *k* array elements (it is allowed to replace the values by any integers). Of course, the changes should make the array as beautiful as possible.

Help Levko and calculate what minimum number *c*(*a*) he can reach.

Input Specification:
The first line contains two integers *n* and *k* (1<=≤<=*k*<=≤<=*n*<=≤<=2000). The second line contains space-separated integers *a*1,<=*a*2,<=... ,<=*a**n* (<=-<=109<=≤<=*a**i*<=≤<=109).

Output Specification:
A single number — the minimum value of *c*(*a*) Levko can get.

Demo Input:
['5 2\n4 7 4 7 4\n', '3 1\n-100 0 100\n', '6 3\n1 2 3 7 8 9\n']

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

Note:
In the first sample Levko can change the second and fourth elements and get array: 4, 4, 4, 4, 4.

In the third sample he can get array: 1, 2, 3, 4, 5, 6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Professor Ibrahim has prepared the final homework for his algorithm’s class. He asked his students to implement the Posterization Image Filter.

Their algorithm will be tested on an array of integers, where the $i$-th integer represents the color of the $i$-th pixel in the image. The image is in black and white, therefore the color of each pixel will be an integer between 0 and 255 (inclusive).

To implement the filter, students are required to divide the black and white color range [0, 255] into groups of consecutive colors, and select one color in each group to be the group’s key. In order to preserve image details, the size of a group must not be greater than $k$, and each color should belong to exactly one group.

Finally, the students will replace the color of each pixel in the array with that color’s assigned group key.

To better understand the effect, here is an image of a basking turtle where the Posterization Filter was applied with increasing $k$ to the right. 

 [Image] 

To make the process of checking the final answer easier, Professor Ibrahim wants students to divide the groups and assign the keys in a way that produces the lexicographically smallest possible array.


-----Input-----

The first line of input contains two integers $n$ and $k$ ($1 \leq n \leq 10^5$, $1 \leq k \leq 256$), the number of pixels in the image, and the maximum size of a group, respectively.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($0 \leq p_i \leq 255$), where $p_i$ is the color of the $i$-th pixel.


-----Output-----

Print $n$ space-separated integers; the lexicographically smallest possible array that represents the image after applying the Posterization filter.


-----Examples-----
Input
4 3
2 14 3 4

Output
0 12 3 3

Input
5 2
0 2 1 255 254

Output
0 1 1 254 254



-----Note-----

One possible way to group colors and assign keys for the first sample:

Color $2$ belongs to the group $[0,2]$, with group key $0$.

Color $14$ belongs to the group $[12,14]$, with group key $12$.

Colors $3$ and $4$ belong to group $[3, 5]$, with group key $3$.

Other groups won't affect the result so they are not listed here.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Sereja and his friends went to a picnic. The guys had *n* soda bottles just for it. Sereja forgot the bottle opener as usual, so the guys had to come up with another way to open bottles.

Sereja knows that the *i*-th bottle is from brand *a**i*, besides, you can use it to open other bottles of brand *b**i*. You can use one bottle to open multiple other bottles. Sereja can open bottle with opened bottle or closed bottle.

Knowing this, Sereja wants to find out the number of bottles they've got that they won't be able to open in any way. Help him and find this number.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=100) — the number of bottles. The next *n* lines contain the bottles' description. The *i*-th line contains two integers *a**i*,<=*b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=1000) — the description of the *i*-th bottle.

Output Specification:
In a single line print a single integer — the answer to the problem.

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

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a program which manipulates a sequence A = {a0, a1, . . . , an−1} with the following operations:

* update(s, t, x): change as, as+1, ..., at to x.
* find(i): output the value of ai.



Note that the initial values of ai (i = 0, 1, . . . , n−1) are 231-1.

Constraints

* 1 ≤ n ≤ 100000
* 1 ≤ q ≤ 100000
* 0 ≤ s ≤ t < n
* 0 ≤ i < n
* 0 ≤ x < 231−1

Input


n q
query1
query2
:
queryq


In the first line, n (the number of elements in A) and q (the number of queries) are given. Then, ith query queryi is given in the following format:


0 s t x


or


1 i


The first digit represents the type of the query. '0' denotes update(s, t, x) and '1' denotes find(i).

Output

For each find operation, print the value.

Examples

Input

3 5
0 0 1 1
0 1 2 3
0 2 2 2
1 0
1 1


Output

1
3


Input

1 3
1 0
0 0 0 5
1 0


Output

2147483647
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has a string S with him. Chef is happy if the string contains a contiguous substring of length strictly greater than 2 in which all its characters are vowels. 

Determine whether Chef is happy or not.

Note that, in english alphabet, vowels are a, e, i, o, and u.

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

- First line will contain T, number of test cases. Then the test cases follow.
- Each test case contains of a single line of input, a string S.

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

For each test case, if Chef is happy, print HAPPY else print SAD.

You may print each character of the string in uppercase or lowercase (for example, the strings hAppY, Happy, haPpY, and HAPPY will all be treated as identical).

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

$1 ≤ T ≤ 1000$
$3 ≤ |S| ≤ 1000$, where $|S|$ is the length of $S$.
$S$ will only contain lowercase English letters.

----- Sample Input 1 ------ 
4
aeiou
abxy
aebcdefghij
abcdeeafg

----- Sample Output 1 ------ 
Happy
Sad
Sad
Happy

----- explanation 1 ------ 
Test case $1$: Since the string aeiou is a contiguous substring and consists of all vowels and has a length $> 2$, Chef is happy.

Test case $2$: Since none of the contiguous substrings of the string consist of all vowels and have a length $> 2$, Chef is sad.

Test case $3$: Since none of the contiguous substrings of the string consist of all vowels and have a length $> 2$, Chef is sad.

Test case $4$: Since the string eea is a contiguous substring and consists of all vowels and has a length $> 2$, Chef is happy.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Complete the square sum function so that it squares each number passed into it and then sums the results together.

For example, for `[1, 2, 2]` it should return `9` because `1^2 + 2^2 + 2^2 = 9`.

```if:racket
In Racket, use a list instead of an array, so '(1 2 3) should return 9.
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string S. Your task is to determine if the sum of ASCII values of all character results in a perfect square or not. If it is a perfect square then the answer is 1, otherwise 0.
Example 1:
Input: S = "d"
Output: 1
Explanation: Sum of ASCII of S is 100 
which is a square number.
Ã¢â¬â¹Example 2:
Input: S = "1Qy"
Output: 0
Explanation: Sum of ASCII of S is
251 which is not a square.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function isSquare() which takes the string S as inputs and returns the answer.
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ |S| ≤ 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Maxim wants to buy an apartment in a new house at Line Avenue of Metropolis. The house has n apartments that are numbered from 1 to n and are arranged in a row. Two apartments are adjacent if their indices differ by 1. Some of the apartments can already be inhabited, others are available for sale.

Maxim often visits his neighbors, so apartment is good for him if it is available for sale and there is at least one already inhabited apartment adjacent to it. Maxim knows that there are exactly k already inhabited apartments, but he doesn't know their indices yet.

Find out what could be the minimum possible and the maximum possible number of apartments that are good for Maxim.


-----Input-----

The only line of the input contains two integers: n and k (1 ≤ n ≤ 10^9, 0 ≤ k ≤ n).


-----Output-----

Print the minimum possible and the maximum possible number of apartments good for Maxim.


-----Example-----
Input
6 3

Output
1 3



-----Note-----

In the sample test, the number of good apartments could be minimum possible if, for example, apartments with indices 1, 2 and 3 were inhabited. In this case only apartment 4 is good. The maximum possible number could be, for example, if apartments with indices 1, 3 and 5 were inhabited. In this case all other apartments: 2, 4 and 6 are good.

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