vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Anthony has two multiple choice assignments to hand in today. The answer to each assignment is a string, where the $i^\textrm {th}$ letter represents the answer to the $i^\textrm {th}$ question.

But instead of handing in two strings, Anthony only hands in a single string. He claims he answered every question correctly but his little sister Cora merged his two strings into a single string. Moreover, Cora merged his string in such a way that the following conditions are satisfied:
 - For any two integers $0\leq i<j<|s_1|$ (where $|s_1|$ is the length of $s_1$), the index of $s_1[i]$ in $s$ is less than the index of $s_1[j]$ in $s$
 - For any two integers $0\leq i<j<|s_2|$, the index of $s_2[i]$ in $s$ is less than the index of $s_2[j]$ in $s$

Can you help Anthony’s teacher verify whether Anthony’s claim is possible?

-----Input-----
The first line contains a single string $s$. It is guaranteed that $2\leq |s|\leq 10000$.

The next two lines contain strings $s_1$ and $s_2$ respectively. It is guaranteed that $1\leq |s_1|, |s_2|\leq 5000$ and $|s_1|+|s_2|=|s|$.

All the strings consists of only lowercase English letters.

-----Output-----
If Anthony’s claim is possible, print “yes” (without quotes). Otherwise, print “no” (without quotes).

-----Examples-----
Sample Input:
aabcad
aba
acd
Sample Output:
yes

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A dragon symbolizes wisdom, power and wealth. On Lunar New Year's Day, people model a dragon with bamboo strips and clothes, raise them with rods, and hold the rods high and low to resemble a flying dragon.

A performer holding the rod low is represented by a 1, while one holding it high is represented by a 2. Thus, the line of performers can be represented by a sequence a_1, a_2, ..., a_{n}.

Little Tommy is among them. He would like to choose an interval [l, r] (1 ≤ l ≤ r ≤ n), then reverse a_{l}, a_{l} + 1, ..., a_{r} so that the length of the longest non-decreasing subsequence of the new sequence is maximum.

A non-decreasing subsequence is a sequence of indices p_1, p_2, ..., p_{k}, such that p_1 < p_2 < ... < p_{k} and a_{p}_1 ≤ a_{p}_2 ≤ ... ≤ a_{p}_{k}. The length of the subsequence is k.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 2000), denoting the length of the original sequence.

The second line contains n space-separated integers, describing the original sequence a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 2, i = 1, 2, ..., n).


-----Output-----

Print a single integer, which means the maximum possible length of the longest non-decreasing subsequence of the new sequence.


-----Examples-----
Input
4
1 2 1 2

Output
4

Input
10
1 1 2 2 2 1 1 2 2 1

Output
9



-----Note-----

In the first example, after reversing [2, 3], the array will become [1, 1, 2, 2], where the length of the longest non-decreasing subsequence is 4.

In the second example, after reversing [3, 7], the array will become [1, 1, 1, 1, 2, 2, 2, 2, 2, 1], where the length of the longest non-decreasing subsequence is 9.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The round carousel consists of $n$ figures of animals. Figures are numbered from $1$ to $n$ in order of the carousel moving. Thus, after the $n$-th figure the figure with the number $1$ follows. Each figure has its own type — the type of the animal corresponding to this figure (the horse, the tiger and so on). The type of animal of the $i$-th figure equals $t_i$. [Image] The example of the carousel for $n=9$ and $t=[5, 5, 1, 15, 1, 5, 5, 1, 1]$. 

You want to color each figure in one of the colors. You think that it's boring if the carousel contains two different figures (with the distinct types of animals) going one right after another and colored in the same color.

Your task is to color the figures in such a way that the number of distinct colors used is the minimum possible and there are no figures of the different types going one right after another and colored in the same color. If you use exactly $k$ distinct colors, then the colors of figures should be denoted with integers from $1$ to $k$.


-----Input-----

The input contains one or more test cases.

The first line contains one integer $q$ ($1 \le q \le 10^4$) — the number of test cases in the test. Then $q$ test cases follow. One test case is given on two lines.

The first line of the test case contains one integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of figures in the carousel. Figures are numbered from $1$ to $n$ in order of carousel moving. Assume that after the $n$-th figure the figure $1$ goes.

The second line of the test case contains $n$ integers $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 2 \cdot 10^5$), where $t_i$ is the type of the animal of the $i$-th figure.

The sum of $n$ over all test cases does not exceed $2\cdot10^5$.


-----Output-----

Print $q$ answers, for each test case print two lines.

In the first line print one integer $k$ — the minimum possible number of distinct colors of figures.

In the second line print $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le k$), where $c_i$ is the color of the $i$-th figure. If there are several answers, you can print any.


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

Output
2
1 2 1 2 2
2
2 1 2 1 2 1
3
2 3 2 3 1
1
1 1 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Even if it's a really easy question, she won't be able to answer it

— Perfect Memento in Strict Sense

Cirno's perfect bitmasks classroom has just started!

Cirno gave her students a positive integer $x$. As an assignment, her students need to find the minimum positive integer $y$, which satisfies the following two conditions:

$$x\ {and}\ y > 0$$ $$x\ {xor}\ y > 0$$

Where ${and}$ is the bitwise AND operation , and ${xor}$ is the bitwise XOR operation .

Among the students was Mystia, who was truly baffled by all these new operators. Please help her!


-----Input-----

The first line of input contains a single integer $t$ ($1 \leq t \leq 10^3$) — the number of input test cases.

For each test case, the only line of input contains one integer $x$ ($1 \leq x \leq 2^{30}$).


-----Output-----

For each test case, print a single integer — the minimum number of $y$.


-----Examples-----

Input
7
1
2
5
9
16
114514
1000000
Output
3
3
1
1
17
2
64


-----Note-----

Test case 1:

$1\; {and}\; 3=1>0$, $1\; {xor}\; 3=2>0$.

Test case 2:

$2\; {and}\; 3=2>0$, $2\; {xor}\; 3=1>0$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice and Bob love playing one-dimensional battle ships. They play on the field in the form of a line consisting of n square cells (that is, on a 1 × n table).

At the beginning of the game Alice puts k ships on the field without telling their positions to Bob. Each ship looks as a 1 × a rectangle (that is, it occupies a sequence of a consecutive squares of the field). The ships cannot intersect and even touch each other.

After that Bob makes a sequence of "shots". He names cells of the field and Alice either says that the cell is empty ("miss"), or that the cell belongs to some ship ("hit").

But here's the problem! Alice like to cheat. May be that is why she responds to each Bob's move with a "miss". 

Help Bob catch Alice cheating — find Bob's first move, such that after it you can be sure that Alice cheated.


-----Input-----

The first line of the input contains three integers: n, k and a (1 ≤ n, k, a ≤ 2·10^5) — the size of the field, the number of the ships and the size of each ship. It is guaranteed that the n, k and a are such that you can put k ships of size a on the field, so that no two ships intersect or touch each other.

The second line contains integer m (1 ≤ m ≤ n) — the number of Bob's moves.

The third line contains m distinct integers x_1, x_2, ..., x_{m}, where x_{i} is the number of the cell where Bob made the i-th shot. The cells are numbered from left to right from 1 to n.


-----Output-----

Print a single integer — the number of such Bob's first move, after which you can be sure that Alice lied. Bob's moves are numbered from 1 to m in the order the were made. If the sought move doesn't exist, then print "-1".


-----Examples-----
Input
11 3 3
5
4 8 6 1 11

Output
3

Input
5 1 3
2
1 5

Output
-1

Input
5 1 3
1
3

Output
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The campus has $m$ rooms numbered from $0$ to $m - 1$. Also the $x$-mouse lives in the campus. The $x$-mouse is not just a mouse: each second $x$-mouse moves from room $i$ to the room $i \cdot x \mod{m}$ (in fact, it teleports from one room to another since it doesn't visit any intermediate room). Starting position of the $x$-mouse is unknown.

You are responsible to catch the $x$-mouse in the campus, so you are guessing about minimum possible number of traps (one trap in one room) you need to place. You are sure that if the $x$-mouse enters a trapped room, it immediately gets caught.

And the only observation you made is $\text{GCD} (x, m) = 1$.


-----Input-----

The only line contains two integers $m$ and $x$ ($2 \le m \le 10^{14}$, $1 \le x < m$, $\text{GCD} (x, m) = 1$) — the number of rooms and the parameter of $x$-mouse. 


-----Output-----

Print the only integer — minimum number of traps you need to install to catch the $x$-mouse.


-----Examples-----
Input
4 3

Output
3

Input
5 2

Output
2



-----Note-----

In the first example you can, for example, put traps in rooms $0$, $2$, $3$. If the $x$-mouse starts in one of this rooms it will be caught immediately. If $x$-mouse starts in the $1$-st rooms then it will move to the room $3$, where it will be caught.

In the second example you can put one trap in room $0$ and one trap in any other room since $x$-mouse will visit all rooms $1..m-1$ if it will start in any of these rooms.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A plane contains a not necessarily convex polygon without self-intersections, consisting of n vertexes, numbered from 1 to n. There is a spider sitting on the border of the polygon, the spider can move like that:

  1. Transfer. The spider moves from the point p1 with coordinates (x1, y1), lying on the polygon border, to the point p2 with coordinates (x2, y2), also lying on the border. The spider can't go beyond the polygon border as it transfers, that is, the spider's path from point p1 to point p2 goes along the polygon border. It's up to the spider to choose the direction of walking round the polygon border (clockwise or counterclockwise). 
  2. Descend. The spider moves from point p1 with coordinates (x1, y1) to point p2 with coordinates (x2, y2), at that points p1 and p2 must lie on one vertical straight line (x1 = x2), point p1 must be not lower than point p2 (y1 ≥ y2) and segment p1p2 mustn't have points, located strictly outside the polygon (specifically, the segment can have common points with the border). 



Initially the spider is located at the polygon vertex with number s. Find the length of the shortest path to the vertex number t, consisting of transfers and descends. The distance is determined by the usual Euclidean metric <image>.

Input

The first line contains integer n (3 ≤ n ≤ 105) — the number of vertexes of the given polygon. Next n lines contain two space-separated integers each — the coordinates of the polygon vertexes. The vertexes are listed in the counter-clockwise order. The coordinates of the polygon vertexes do not exceed 104 in their absolute value. 

The last line contains two space-separated integers s and t (1 ≤ s, t ≤ n) — the start and the end vertexes of the sought shortest way. 

Consider the polygon vertexes numbered in the order they are given in the input, that is, the coordinates of the first vertex are located on the second line of the input and the coordinates of the n-th vertex are on the (n + 1)-th line. It is guaranteed that the given polygon is simple, that is, it contains no self-intersections or self-tangencies.

Output

In the output print a single real number — the length of the shortest way from vertex s to vertex t. The answer is considered correct, if its absolute or relative error does not exceed 10 - 6.

Examples

Input

4
0 0
1 0
1 1
0 1
1 4


Output

1.000000000000000000e+000


Input

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


Output

0.000000000000000000e+000


Input

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


Output

5.650281539872884700e+000

Note

In the first sample the spider transfers along the side that connects vertexes 1 and 4.

In the second sample the spider doesn't have to transfer anywhere, so the distance equals zero.

In the third sample the best strategy for the spider is to transfer from vertex 3 to point (2,3), descend to point (2,1), and then transfer to vertex 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Math geeks and computer nerds love to anthropomorphize numbers and assign emotions and personalities to them. Thus there is defined the concept of a "happy" number. A happy number is defined as an integer in which the following sequence ends with the number 1.

* Start with the number itself.
* Calculate the sum of the square of each individual digit.
* If the sum is equal to 1, then the number is happy. If the sum is not equal to 1, then repeat steps 1 and 2. A number is considered unhappy once the same number occurs multiple times in a sequence because this means there is a loop and it will never reach 1.

For example, the number 7 is a "happy" number:

7^(2) = 49 --> 4^(2) + 9^(2) = 97 --> 9^(2) + 7^(2) = 130 --> 1^(2) + 3^(2) + 0^(2) = 10 --> 1^(2) + 0^(2) = 1

Once the sequence reaches the number 1, it will stay there forever since 1^(2) = 1

On the other hand, the number 6 is not a happy number as the sequence that is generated is the following: 6, 36, 45, 41, 17, 50, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, 89

Once the same number occurs twice in the sequence, the sequence is
guaranteed to go on infinitely, never hitting the number 1, since it repeat
this cycle.

Your task is to write a program which will print a list of all happy numbers between 1 and x (both inclusive), where:
```python
2 <= x <= 5000
```

___

Disclaimer: This Kata is an adaptation of a HW assignment I had for McGill University's COMP 208 (Computers in Engineering) class.

___

If you're up for a challenge, you may want to try a [performance version of this kata](https://www.codewars.com/kata/happy-numbers-performance-edition) by FArekkusu.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The hamming distance of two equal-length strings is the number of positions, in which the two string differ. In other words, the number of character substitutions required to transform one string into the other. 

For this first Kata, you will write a function ```hamming_distance(a, b)``` with two equal-length strings containing only 0s and 1s as parameters. There is no need to test the parameters for validity (but you can, if you want).The function's output should be the hamming distance of the two strings as an integer.

Example:

```python
hamming_distance('100101', '101001') == 2
hamming_distance('1010', '0101') == 4
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In order to fly to the Moon Mister B just needs to solve the following problem.

There is a complete indirected graph with n vertices. You need to cover it with several simple cycles of length 3 and 4 so that each edge is in exactly 2 cycles.

We are sure that Mister B will solve the problem soon and will fly to the Moon. Will you?


-----Input-----

The only line contains single integer n (3 ≤ n ≤ 300).


-----Output-----

If there is no answer, print -1.

Otherwise, in the first line print k (1 ≤ k ≤ n^2) — the number of cycles in your solution.

In each of the next k lines print description of one cycle in the following format: first print integer m (3 ≤ m ≤ 4) — the length of the cycle, then print m integers v_1, v_2, ..., v_{m} (1 ≤ v_{i} ≤ n) — the vertices in the cycle in the traverse order. Each edge should be in exactly two cycles.


-----Examples-----
Input
3

Output
2
3 1 2 3
3 1 2 3

Input
5

Output
6
3 5 4 2
3 3 1 5
4 4 5 2 3
4 4 3 2 1
3 4 2 1
3 3 1 5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Amit is going on a date and he wants to gift his date an array of positive numbers. But he is running short on money. He already has an array of numbers in design. Cost of an array of numbers is the sum of elements in it. But he wants to minimize the cost of making it. 
So he does the following number of operations one by one for any number of times:
He chooses two adjacent elements ,replace them by one element with value = XOR of the two numbers. This operation reduces length of array (and elements are re-numerated accordingly)
Find the minimum amount of money that Amit needs to spend to gift his date.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of $2$ lines of input, first line contains a single integer $N$ and the second line contains $N$ elements - $A1,A2,A3,.....,AN$ 

-----Output:-----
For each testcase, output in a single line answer denoting the minimum cost

-----Constraints-----
- $1 \leq T \leq 10$
- $1 \leq N \leq 10^5$
- $0 \leq Ai \leq 10^9$ for $1\leq i \leq N$

-----Sample Input:-----
3
5
8 4 1 5 0
5
1 2 4 0 8
2
10 10

-----Sample Output:-----
8
15
0

-----EXPLANATION:-----
For first case,
This array is :
$[8,4,1,5,0] -> [8,4,4,0] -> [8,0,0]$. Sum=$8$ So the answer is 8.

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

Koa the Koala initially has $n+1$ strings $s_1, s_2, \dots, s_{n+1}$.

For each $i$ ($1 \le i \le n$) she calculated $a_i$ — the length of the longest common prefix of $s_i$ and $s_{i+1}$.

Several days later Koa found these numbers, but she couldn't remember the strings.

So Koa would like to find some strings $s_1, s_2, \dots, s_{n+1}$ which would have generated numbers $a_1, a_2, \dots, a_n$. Can you help her?

If there are many answers print any. We can show that answer always exists for the given constraints. 


-----Input-----

Each test contains multiple test cases. The first line contains $t$ ($1 \le t \le 100$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 100$) — the number of elements in the list $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 50$) — the elements of $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $100$.


-----Output-----

For each test case:

Output $n+1$ lines. In the $i$-th line print string $s_i$ ($1 \le |s_i| \le 200$), consisting of lowercase Latin letters. Length of the longest common prefix of strings $s_i$ and $s_{i+1}$ has to be equal to $a_i$.

If there are many answers print any. We can show that answer always exists for the given constraints.


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

Output
aeren
ari
arousal
around
ari
monogon
monogamy
monthly
kevinvu
kuroni
kurioni
korone
anton
loves
adhoc
problems


-----Note-----

In the $1$-st test case one of the possible answers is $s = [aeren, ari, arousal, around, ari]$.

Lengths of longest common prefixes are:  Between $\color{red}{a}eren$ and $\color{red}{a}ri$ $\rightarrow 1$  Between $\color{red}{ar}i$ and $\color{red}{ar}ousal$ $\rightarrow 2$  Between $\color{red}{arou}sal$ and $\color{red}{arou}nd$ $\rightarrow 4$  Between $\color{red}{ar}ound$ and $\color{red}{ar}i$ $\rightarrow 2$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After passing the final round of the Hunter Exam, Gon is now a Hunter! But before continuing his exciting journey, Gon decides to visit his home in ‘While Island’.

Aunt Mito is happy that Gon has become a Hunter and has visited home. But at the same time, she feels worried about Gon — the life of a Hunter is challenging. Thus, she will not allow Gon to leave ‘While Island’, unless Gon is able to solve a puzzle prepared by aunt Mito.

But what puzzle should Mito give to Gon? Mito opened ‘IMO 2019 Problems’ and found the following problem:

The Bank of Bath issues coins with an $H$ on one side and a $T$ on the other. Prof. Tuy has $n$ of these coins arranged in a line from left to right. He repeatedly performs the following operation: if there are exactly $k > 0$ coins showing $H$, then he turns over the $k$-th coin from the left; otherwise, all coins show $T$ and he stops. For example, if $n = 3$ the process starting with the configuration $THT$ would be: $THT \rightarrow HHT \rightarrow HTT \rightarrow TTT$, which stops after three operations.

Show that, for each initial configuration, Prof. Tuy stops after a finite number of operations.

‘This problem is too easy’ — Mito thought. ‘Gon will be able to solve it in no time’.

After some more thinking, Mito changed the above problem to the following harder version:

For each initial configuration $C$, let $L(C)$ be the number of operations before Prof. Tuy stops.

Given a sequence $S$ consisting of $H$, $T$ and $?$, representing some initial state, where $?$ denotes an unknown state. Calculate the average value of $L(C)$ over all possible sequences $C$ represented by $S$.

Even though Gon is smart, he is still unable to solve this question. Please help Gon!

-----Input-----
The input contains a single non-empty line with at most $10^6$ characters — the sequence $S$.

-----Output-----
The output must contain a single number — the average value of $L(C)$, as explained in the statement.

Your answer will be considered correct if its relative or absolute error doesn’t exceed $10^{-6}$.

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

-----Examples-----
Sample Input 1:
HH
Sample Output 1:
2.0

Sample Input 2:
H?
Sample Output 2:
1.5

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