vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Mirko purchased a new microprocessor. Unfortunately, he soon learned that many of his programs that he wrote for his old processor didn’t work on the new processor.

Deep inside the technical documentation for both processors, he found an explanation. In order to work faster, the new processor imposes certain constraints on the machine code of programs, constraints that never existed on the previous model.

The machine code of a processor consists of instructions that are executed sequentially. Each instruction uses a byte of memory. Also, instructions can have zero or more parameters, each of which uses an additional byte of memory. In machine code, parameters immediately follow an instruction.

When formatted as text, machine code instructions are uppercase letters, while parameters are lowercase letters. For example:

A

b

c

b

B

c

c

C

D

e

f

g

h

This program consists of four instructions; the first takes three parameters, the second two, the third none and the fourth takes four parameters. The program uses $13$ bytes of memory.

The new processor model fetches memory in four-byte chunks so each instruction must start at a memory address that is divisible by four (the first byte in memory is address $0$). To achieve that, we can insert NOP (no operation) instructions into the old program, instructions that do nothing and are not limited to memory locations divisible by four. The above program, adapted to run on the new processor, can look like this:

A

b

c

b

B

c

c

NOP

C

NOP

NOP

NOP

D

e

f

g

h

The instructions A, B, C and D are now at memory locations $0$, $4$, $8$ and $12$, which satisfies the processor’s constraints.

Write a program that determines the smallest number of NOP instructions that need to be inserted for the given program to work on the new processor model.

-----Input-----
The input contains the machine code of the program written for the old processor model. The program will consist of at most $200$ English letters.

The program will always start in an instruction, i.e., the first letter in the machine code will be uppercase. If an instruction appears more than once in the machine code, it will always take the same number of parameters.

-----Output-----
Output the smallest number of NOP instructions needed to adapt the program for the new processor.

-----Examples-----
Sample Input 1:
Abcd
Sample Output 1:
0

Sample Input 2:
EaEbFabG
Sample Output 2:
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an odd number in the form of string, the task is to make largest even number possible from the given number provided one is allowed to do only one swap operation, if no such number is possible then return the input string itself.
Example 1:
Input:
s = 4543
Output: 4534
Explanation: Swap 4(3rd pos) and 3.
 
Example 2:
Input:
s = 1539
Output: 1539
Explanation: No even no. present.
 
Your Task:  
You dont need to read input or print anything. Complete the function makeEven() which takes a string s as input parameter and returns a string after performing given operations.
 
Expected Time Complexity: O(Length of Input string).
Expected Auxiliary Space: O(1).
 
Constraints:
1 <= Length of odd number string<= 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Word $s$ of length $n$ is called $k$-complete if   $s$ is a palindrome, i.e. $s_i=s_{n+1-i}$ for all $1 \le i \le n$;  $s$ has a period of $k$, i.e. $s_i=s_{k+i}$ for all $1 \le i \le n-k$. 

For example, "abaaba" is a $3$-complete word, while "abccba" is not.

Bob is given a word $s$ of length $n$ consisting of only lowercase Latin letters and an integer $k$, such that $n$ is divisible by $k$. He wants to convert $s$ to any $k$-complete word.

To do this Bob can choose some $i$ ($1 \le i \le n$) and replace the letter at position $i$ with some other lowercase Latin letter.

So now Bob wants to know the minimum number of letters he has to replace to convert $s$ to any $k$-complete word.

Note that Bob can do zero changes if the word $s$ is already $k$-complete.

You are required to answer $t$ test cases independently.


-----Input-----

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

The first line of each test case contains two integers $n$ and $k$ ($1 \le k < n \le 2 \cdot 10^5$, $n$ is divisible by $k$).

The second line of each test case contains a word $s$ of length $n$.

It is guaranteed that word $s$ only contains lowercase Latin letters. And it is guaranteed that the sum of $n$ over all test cases will not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, output one integer, representing the minimum number of characters he has to replace to convert $s$ to any $k$-complete word.


-----Example-----
Input
4
6 2
abaaba
6 3
abaaba
36 9
hippopotomonstrosesquippedaliophobia
21 7
wudixiaoxingxingheclp

Output
2
0
23
16



-----Note-----

In the first test case, one optimal solution is aaaaaa.

In the second test case, the given word itself is $k$-complete.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Bob recently read about bitwise operations used in computers: AND, OR and XOR. He have studied their properties and invented a new game.

Initially, Bob chooses integer *m*, bit depth of the game, which means that all numbers in the game will consist of *m* bits. Then he asks Peter to choose some *m*-bit number. After that, Bob computes the values of *n* variables. Each variable is assigned either a constant *m*-bit number or result of bitwise operation. Operands of the operation may be either variables defined before, or the number, chosen by Peter. After that, Peter's score equals to the sum of all variable values.

Bob wants to know, what number Peter needs to choose to get the minimum possible score, and what number he needs to choose to get the maximum possible score. In both cases, if there are several ways to get the same score, find the minimum number, which he can choose.

Input Specification:
The first line contains two integers *n* and *m*, the number of variables and bit depth, respectively (1<=≤<=*n*<=≤<=5000; 1<=≤<=*m*<=≤<=1000). 

The following *n* lines contain descriptions of the variables. Each line describes exactly one variable. Description has the following format: name of a new variable, space, sign ":=", space, followed by one of:
 1.  Binary number of exactly *m* bits. 1.  The first operand, space, bitwise operation ("AND", "OR" or "XOR"), space, the second operand. Each operand is either the name of variable defined before or symbol '?', indicating the number chosen by Peter. 
Variable names are strings consisting of lowercase Latin letters with length at most 10. All variable names are different.

Output Specification:
In the first line output the minimum number that should be chosen by Peter, to make the sum of all variable values minimum possible, in the second line output the minimum number that should be chosen by Peter, to make the sum of all variable values maximum possible. Both numbers should be printed as *m*-bit binary numbers.

Demo Input:
['3 3\na := 101\nb := 011\nc := ? XOR b\n', '5 1\na := 1\nbb := 0\ncx := ? OR a\nd := ? XOR ?\ne := d AND bb\n']

Demo Output:
['011\n100\n', '0\n0\n']

Note:
In the first sample if Peter chooses a number 011<sub class="lower-index">2</sub>, then *a* = 101<sub class="lower-index">2</sub>, *b* = 011<sub class="lower-index">2</sub>, *c* = 000<sub class="lower-index">2</sub>, the sum of their values is 8. If he chooses the number 100<sub class="lower-index">2</sub>, then *a* = 101<sub class="lower-index">2</sub>, *b* = 011<sub class="lower-index">2</sub>, *c* = 111<sub class="lower-index">2</sub>, the sum of their values is 15.

For the second test, the minimum and maximum sum of variables *a*, *bb*, *cx*, *d* and *e* is 2, and this sum doesn't depend on the number chosen by Peter, so the minimum Peter can choose is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a given array $a_1, a_2, a_3, ... , a_N$ of $N$ elements and an integer $K$, find the smallest sub-array size (smallest window length) where the elements in the sub-array contains all integers in range [$1, 2, ..., K$]. If there is no such sub-array, report 0.

Constraints

* $1 \leq N \leq 10^5$
* $1 \leq K \leq 10^5$
* $1 \leq a_i \leq 10^5$

Input

The input is given in the following format.

$N$ $K$
$a_1$ $a_2$ ... $a_N$

Output

Print the smallest sub-array size in a line.

Examples

Input

6 2
4 1 2 1 3 5


Output

2


Input

6 3
4 1 2 1 3 5


Output

3


Input

3 4
1 2 3


Output

0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a number X, let its "Coolness" be defined as the number of "101"s occurring in its binary representation. For example, the number 21 has Coolness 2, since its binary representation is 101012, and the string "101" occurs twice in this representation.

A number is defined as Very Cool if its Coolness is greater than or equal to K. Please, output the number of Very Cool integers between 1 and R.

Input:

The first line contains an integer T, the number of test cases. 
The next T lines contains two space-separated integers, R and K. 

Output:

Output T lines, the answer for each test case. 

Constraints:

1 ≤ T ≤ 100 

1 ≤ R ≤ 105 

1 ≤ K ≤ 100

SAMPLE INPUT
1
5 1

SAMPLE OUTPUT
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A point (x,y), on the cartesian plane, makes an angle theta with the positive direction of the x-axis. Theta varies in the interval  [0 ,2PI) radians, i.e, greater than or equal to zero; but less than 2*PI radians.  

For example, the polar angle of the point (1,2) as marked in this plane below, is (approximately) 63.4 degrees (multiply by PI/180 to convert to radians)

Ref http://eldar.mathstat.uoguelph.ca/dashlock/Outreach/Articles/images/PRfig1.jpg  

The Task  

Given a list of points in the 2D plane, sort them in ascending order of their polar angle. In case multiple points share exactly the same polar angle, the one with lesser distance from the origin (0,0) should occur earlier in the sorted list.  

Input Format 

The first line contains an integer N. 

This is followed by N lines containing pairs of space separated integers, x and y which represent the coordinates of the points in the cartesian plane.  

Constraints 

    1 <= N <= 1000 

    -100 <= x,y <= 100 

    The point (0,0) will not be present in the list of points.  

Output Format 

The output should contain N lines. 
Each line should contain two integers x and y, corresponding to a point in the original list. Display the points in ascending order of their polar angle.

Sample Input 

4  
1 0  
0 -1  
-1 0  
0 1  

Sample Output    

1 0    
0 1    
-1 0    
0 -1    

Explanation  

The point (0,1) has a polar angle of 90 degrees. The point (1,0) has a polar angle of 0 degrees. (-1,0) has a polar angle of 180 degrees and (0,-1) has a polar angle of 270 degrees.

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

Problem Statement:

Jacob’s friend Victor likes to watch soap ‘White Collar’ .An intriguing episode is about to start, and he hasn't scrubbed his plate yet .So he ultimately decided to at least put it under the tap to be filled with water .The plate can be represented by a parallelepiped n×p×q, i.e, it has n  layers (the last layer is the bottom one and the first layer is the upper one), each of which is a rectangle of  p × q with empty squares ('.') and blockades ('#'). However the water can only be present in the empty squares. Victor positioned the tap in a way such that it is above the square (x,y) of the first layer (assume that this square(x, y) is empty). In every minute a cubical unit of water from the tap falls into the plate. Your task is to find out in exactly how many minutes should victor unglue himself from the soap White Collar and turn the water off for it not to overfill the plate. That is, you should find the moment of time when the plate is completely full and is about to overfill in the next moment.

Note: The water fills all the area within reach (see test case 4). Water flows in each of the 6 directions/faces of the given cube with dimension 1 x 1 x 1.

Input : 

The first line contains T – No of test cases (1 ≤ T ≤ 25).

Next T lines contain three numbers n, p, q (1 ≤ n, p, q ≤10) which are the sizes of the plate. Then follow n rectangles where each rectangle consist of p lines each containing q characters either '.' or '#', which represents the "layers" of the plate in that order from the top to the bottom. The rectangles are separated by empty lines (see the sample test cases). The last line contains x and y (1 ≤ x ≤ p,1 ≤ y ≤ q) which are the tap's coordinates. x is the number of the row and y is the number of the column. Rows of each layer are numbered from left to right by the integers from 1 to p and columns of each layer are numbered from top to bottom by the integers from 1 to q.

Output :

T lines of output should contain an integer, showing exactly in how many minutes the plate will be filled completely with water.

SAMPLE INPUT
5
1 1 1

.

1 1
2 1 1

.

#

1 1
2 2 2

.#
##

..
..

1 1
3 2 2

#.
##

#.
.#

..
..

1 2
3 3 3

.#.
###
##.

.##
###
##.

...
...
...

1 1

SAMPLE OUTPUT
1
1
5
7
13

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Santa Claus decided to disassemble his keyboard to clean it. After he returned all the keys back, he suddenly realized that some pairs of keys took each other's place! That is, Santa suspects that each key is either on its place, or on the place of another key, which is located exactly where the first key should be. 

In order to make sure that he's right and restore the correct order of keys, Santa typed his favorite patter looking only to his keyboard.

You are given the Santa's favorite patter and the string he actually typed. Determine which pairs of keys could be mixed. Each key must occur in pairs at most once.


-----Input-----

The input consists of only two strings s and t denoting the favorite Santa's patter and the resulting string. s and t are not empty and have the same length, which is at most 1000. Both strings consist only of lowercase English letters.


-----Output-----

If Santa is wrong, and there is no way to divide some of keys into pairs and swap keys in each pair so that the keyboard will be fixed, print «-1» (without quotes).

Otherwise, the first line of output should contain the only integer k (k ≥ 0) — the number of pairs of keys that should be swapped. The following k lines should contain two space-separated letters each, denoting the keys which should be swapped. All printed letters must be distinct.

If there are several possible answers, print any of them. You are free to choose the order of the pairs and the order of keys in a pair.

Each letter must occur at most once. Santa considers the keyboard to be fixed if he can print his favorite patter without mistakes.


-----Examples-----
Input
helloworld
ehoolwlroz

Output
3
h e
l o
d z

Input
hastalavistababy
hastalavistababy

Output
0

Input
merrychristmas
christmasmerry

Output
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given is a directed graph G with N vertices and M edges.
The vertices are numbered 1 to N, and the i-th edge is directed from Vertex A_i to Vertex B_i.
It is guaranteed that the graph contains no self-loops or multiple edges.

Determine whether there exists an induced subgraph (see Notes) of G such that the in-degree and out-degree of every vertex are both 1. If the answer is yes, show one such subgraph.
Here the null graph is not considered as a subgraph.

Constraints

* 1 \leq N \leq 1000
* 0 \leq M \leq 2000
* 1 \leq A_i,B_i \leq N
* A_i \neq B_i
* All pairs (A_i, B_i) are distinct.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N M
A_1 B_1
A_2 B_2
:
A_M B_M


Output

If there is no induced subgraph of G that satisfies the condition, print `-1`. Otherwise, print an induced subgraph of G that satisfies the condition, in the following format:


K
v_1
v_2
:
v_K


This represents the induced subgraph of G with K vertices whose vertex set is \\{v_1, v_2, \ldots, v_K\\}. (The order of v_1, v_2, \ldots, v_K does not matter.) If there are multiple subgraphs of G that satisfy the condition, printing any of them is accepted.

Examples

Input

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


Output

3
1
2
4


Input

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


Output

-1


Input

6 9
1 2
2 3
3 4
4 5
5 6
5 1
5 2
6 1
6 2


Output

4
2
3
4
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a set of n pens, each of them can be red, blue, green, orange, and violet in color. Count a minimum number of pens that should be taken out from the set so that any two neighboring pens have different colors. Pens are considered to be neighboring if there are no other pens between them.

-----Input:-----
- 
The first line contains t denoting the number of test cases.
- 
The first line of each test case will contain a single integer n.
- 
The second line of each test case will contain a string s.
(s contains only 'R', 'B', 'G', 'O', and 'V' characters denoting red, blue, green, orange, and violet respectively)

-----Output:-----
For each test case, print single line containing one integer - The minimum number of pens that need to be taken out.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq n \leq 1000$

-----Sample Input:-----
2
5
RBBRG
5
RBGOV

-----Sample Output:-----
1
0

-----EXPLANATION:-----
In first test case, two blue pens are neighboring each other, if we take out any one of them then the string will be RBRG in which each pen has different neighbors.
In second test case, no pen needs to be taken out as each pen has different neighbors.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The next lecture in a high school requires two topics to be discussed. The $i$-th topic is interesting by $a_i$ units for the teacher and by $b_i$ units for the students.

The pair of topics $i$ and $j$ ($i < j$) is called good if $a_i + a_j > b_i + b_j$ (i.e. it is more interesting for the teacher).

Your task is to find the number of good pairs of topics.


-----Input-----

The first line of the input contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of topics.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the interestingness of the $i$-th topic for the teacher.

The third line of the input contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^9$), where $b_i$ is the interestingness of the $i$-th topic for the students.


-----Output-----

Print one integer — the number of good pairs of topic.


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

Output
7

Input
4
1 3 2 4
1 3 2 4

Output
0

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One day Dima and Alex had an argument about the price and quality of laptops. Dima thinks that the more expensive a laptop is, the better it is. Alex disagrees. Alex thinks that there are two laptops, such that the price of the first laptop is less (strictly smaller) than the price of the second laptop but the quality of the first laptop is higher (strictly greater) than the quality of the second laptop.

Please, check the guess of Alex. You are given descriptions of *n* laptops. Determine whether two described above laptops exist.

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=105) — the number of laptops.

Next *n* lines contain two integers each, *a**i* and *b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*), where *a**i* is the price of the *i*-th laptop, and *b**i* is the number that represents the quality of the *i*-th laptop (the larger the number is, the higher is the quality).

All *a**i* are distinct. All *b**i* are distinct.

Output Specification:
If Alex is correct, print "Happy Alex", otherwise print "Poor Alex" (without the quotes).

Demo Input:
['2\n1 2\n2 1\n']

Demo Output:
['Happy Alex\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The name of our college is "Government College of Engineering and Textile Technology Berhampore". There is another college named "Government College of Engineering and Textile Technology Serampore". As the names are quite similar, those who are unaware of existence of both the colleges, often get confused. And mistake one with other.

Given a string, if it contains the word berhampore (case insensitive), print GCETTB or if it contains serampore(case-insensitive), print GCETTS . If the string contains neither print Others. If it contains both Berhampore and Serampore print Both 
Input 
- First line contains single integer T, No. of test case  
- Next line for every test contain case a string S 
Output

Print GCETTB or GCETTS or Others or Both on a new line
Constraints 
- 1 <= T <= 10 
- 0 <= len(S) <= 100  
- S contain a-z and A-Z and space only
Sample Input
3
Government clg Berhampore
SeRaMporE textile college 
Girls college Kolkata

Sample Output

GCETTB

GCETTS

Others       
Explanation

Self-Explanatory

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Pashmak and Parmida's problem

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Parmida is a clever girl and she wants to participate in Olympiads this year. Of course she wants her partner to be clever too (although he's not)! Parmida has prepared the following test problem for Pashmak.

There is a sequence *a* that consists of *n* integers *a*1,<=*a*2,<=...,<=*a**n*. Let's denote *f*(*l*,<=*r*,<=*x*) the number of indices *k* such that: *l*<=≤<=*k*<=≤<=*r* and *a**k*<==<=*x*. His task is to calculate the number of pairs of indicies *i*,<=*j* (1<=≤<=*i*<=&lt;<=*j*<=≤<=*n*) such that *f*(1,<=*i*,<=*a**i*)<=&gt;<=*f*(*j*,<=*n*,<=*a**j*).

Help Pashmak with the test.

Input Specification:
The first line of the input contains an integer *n* (1<=≤<=*n*<=≤<=106). The second line contains *n* space-separated integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=109).

Output Specification:
Print a single integer — the answer to the problem.

Demo Input:
['7\n1 2 1 1 2 2 1\n', '3\n1 1 1\n', '5\n1 2 3 4 5\n']

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

Note:
none

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