vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A robber has attempted to rob a bank but failed to complete his task. However, he had managed to open all the safes.

Oleg the bank client loves money (who doesn't), and decides to take advantage of this failed robbery and steal some money from the safes. There are many safes arranged in a line, where the i-th safe from the left is called safe i. There are n banknotes left in all the safes in total. The i-th banknote is in safe x_{i}. Oleg is now at safe a. There are two security guards, one of which guards the safe b such that b < a, i.e. the first guard is to the left of Oleg. The other guard guards the safe c so that c > a, i.e. he is to the right of Oleg.

The two guards are very lazy, so they do not move. In every second, Oleg can either take all the banknotes from the current safe or move to any of the neighboring safes. However, he cannot visit any safe that is guarded by security guards at any time, becaues he might be charged for stealing. Determine the maximum amount of banknotes Oleg can gather.


-----Input-----

The first line of input contains three space-separated integers, a, b and c (1 ≤ b < a < c ≤ 10^9), denoting the positions of Oleg, the first security guard and the second security guard, respectively.

The next line of input contains a single integer n (1 ≤ n ≤ 10^5), denoting the number of banknotes.

The next line of input contains n space-separated integers x_1, x_2, ..., x_{n} (1 ≤ x_{i} ≤ 10^9), denoting that the i-th banknote is located in the x_{i}-th safe. Note that x_{i} are not guaranteed to be distinct.


-----Output-----

Output a single integer: the maximum number of banknotes Oleg can take.


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

Output
4

Input
6 5 7
5
1 5 7 92 3

Output
0



-----Note-----

In the first example Oleg can take the banknotes in positions 4, 5, 6 (note that there are 2 banknotes at position 5). Oleg can't take the banknotes in safes 7 and 8 because he can't run into the second security guard. Similarly, Oleg cannot take the banknotes at positions 3 and 2 because he can't run into the first security guard. Thus, he can take a maximum of 4 banknotes.

For the second sample, Oleg can't take any banknotes without bumping into any of the security guards.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
I decided to play rock-paper-scissors with a group of five good friends. Rock-paper-scissors has three hands: goo, choki, and par. If the game between goo and choki is a match between goo and choki, goo is "winning" and choki is "losing". , Par and Goo have the rule that Par is "winning" and Goo is "losing". If everyone has the same hand, or if all of Goo, Choki, and Par come out, it will be "Aiko".

Create a program that inputs the hands of five rock-paper-scissors players and outputs the wins and losses of each person. Rock-paper-scissors hands are represented by the numbers 1 for goo, 2 for choki, and 3 for par. Win / loss is represented by a number of 1, "win" is 1, "los" is 2, and "Aiko" is 3, and they are output according to the input order.



Input

A sequence of multiple datasets is given as input. The end of the input is indicated by a single line of zeros. Each dataset is given in the following format:


h1
h2
h3
h4
h5


The i-th line is given the i-th hand hi (1, 2 or 3).

The number of datasets does not exceed 200.

Output

Outputs the wins and losses of 5 players for each input dataset. Output the win / loss (1, 2 or 3) of the i-th person on the i-line.

Example

Input

1
2
3
2
1
1
2
2
2
1
0


Output

3
3
3
3
3
1
2
2
2
1

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You're given a matrix *A* of size *n*<=×<=*n*.

Let's call the matrix with nonnegative elements magic if it is symmetric (so *a**ij*<==<=*a**ji*), *a**ii*<==<=0 and *a**ij*<=≤<=*max*(*a**ik*,<=*a**jk*) for all triples *i*,<=*j*,<=*k*. Note that *i*,<=*j*,<=*k* do not need to be distinct.

Determine if the matrix is magic.

As the input/output can reach very huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=2500) — the size of the matrix *A*.

Each of the next *n* lines contains *n* integers *a**ij* (0<=≤<=*a**ij*<=&lt;<=109) — the elements of the matrix *A*.

Note that the given matrix not necessarily is symmetric and can be arbitrary.

Output Specification:
Print ''MAGIC" (without quotes) if the given matrix *A* is magic. Otherwise print ''NOT MAGIC".

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

Demo Output:
['MAGIC\n', 'NOT MAGIC\n', 'NOT MAGIC\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The aim of this kata is to split a given string into different strings of equal size (note size of strings is passed to the method)

Example:

    Split the below string into other strings of size #3

    'supercalifragilisticexpialidocious'

    Will return a new string
    'sup erc ali fra gil ist ice xpi ali doc iou s'


Assumptions:

    String length is always greater than 0
    String has no spaces
    Size is always positive

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Abhi and his friends (Shanky,Anku and Pandey) love to play with strings. Abhi invented a simple game. He will give a string S to his friends. Shanky and Anku will play the game while Pandey is just a spectator. Shanky will traverse the string from beginning (left to right) while Anku will traverse from last (right to left). Both have to find the first character they encounter during their traversal,that appears only once in the entire string. Winner will be one whose character is alphabetically more superior(has higher ASCII value). When it is not possible to decide the winner by comparing their characters, Pandey will be the winner.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

Each test case contains a string S having only lowercase alphabets ( a..z ).

-----Output-----
For each test case, output a single line containing "SHANKY" if Shanky is the winner or "ANKU" if Anku is the winner or "PANDEY" if the winner is Pandey. Output your answer without quotes.

-----Constraints-----
- 1 ≤ T ≤ 100
- 1 < |S| ≤ 10^5

-----Example-----
Input:
3
google
breakraekb
aman

Output:
SHANKY
PANDEY
ANKU

-----Explanation-----
Example case 2. Both Shanky and Anku can not find any such character. Hence it is not possible to decide the winner between these two. So Pandey is the winner.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasya, or Mr. Vasily Petrov is a dean of a department in a local university. After the winter exams he got his hands on a group's gradebook.

Overall the group has *n* students. They received marks for *m* subjects. Each student got a mark from 1 to 9 (inclusive) for each subject.

Let's consider a student the best at some subject, if there is no student who got a higher mark for this subject. Let's consider a student successful, if there exists a subject he is the best at.

Your task is to find the number of successful students in the group.

Input Specification:
The first input line contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=100) — the number of students and the number of subjects, correspondingly. Next *n* lines each containing *m* characters describe the gradebook. Each character in the gradebook is a number from 1 to 9. Note that the marks in a rows are not sepatated by spaces.

Output Specification:
Print the single number — the number of successful students in the given group.

Demo Input:
['3 3\n223\n232\n112\n', '3 5\n91728\n11828\n11111\n']

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

Note:
In the first sample test the student number 1 is the best at subjects 1 and 3, student 2 is the best at subjects 1 and 2, but student 3 isn't the best at any subject.

In the second sample test each student is the best at at least one subject.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mario is making up silly games again instead of reading Dostoevsky for school. The rules of his newest game follow. First he chooses a random word from the book. Then he splits the word in two arbitrary places to get three separate words. After that he reverses the order of the letters in each of those three words (exchanges the first and last letters, the second and second last and so on).

Finally, he puts the three words back together in the same order in which they were before splitting. The goal of the game is to obtain the lexicographically smallest word possible. In other words, of all words that can be obtained by the above procedure, find one which would be earliest in a dictionary.

Write a program that plays Mario’s game perfectly.

-----Input-----
The first and only line of input contains Mario’s chosen word, a string of lowercase letters of the English alphabet with no spaces.

The input word will be between $3$ and $50$ characters long (inclusive).

-----Output-----
Output the best word on a single line.

-----Examples-----
Sample Input 1:
dcbagfekjih
Sample Output 1:
abcdefghijk

Sample Input 2:
mobitel
Sample Output 2:
bometil

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For this kata, you are given three points ```(x1,y1,z1)```, ```(x2,y2,z2)```, and ```(x3,y3,z3)``` that lie on a straight line in 3-dimensional space.
You have to figure out which point lies in between the other two.

Your function should return 1, 2, or 3 to indicate which point is the in-between one.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You work in a big office. It is a 9 floor building with an elevator that can accommodate up to 4 people. It is your responsibility to manage this elevator.

Today you are late, so there are queues on some floors already. For each person you know the floor where he currently is and the floor he wants to reach. Also, you know the order in which people came to the elevator.

According to the company's rules, if an employee comes to the elevator earlier than another one, he has to enter the elevator earlier too (even if these employees stay on different floors). Note that the employees are allowed to leave the elevator in arbitrary order.

The elevator has two commands:   Go up or down one floor. The movement takes 1 second.  Open the doors on the current floor. During this operation all the employees who have reached their destination get out of the elevator. Then all the employees on the floor get in the elevator in the order they are queued up while it doesn't contradict the company's rules and there is enough space in the elevator. Each employee spends 1 second to get inside and outside the elevator. 

Initially the elevator is empty and is located on the floor 1.

You are interested what is the minimum possible time you need to spend to deliver all the employees to their destination. It is not necessary to return the elevator to the floor 1.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 2000) — the number of employees.

The i-th of the next n lines contains two integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ 9, a_{i} ≠ b_{i}) — the floor on which an employee initially is, and the floor he wants to reach.

The employees are given in the order they came to the elevator.


-----Output-----

Print a single integer — the minimal possible time in seconds.


-----Examples-----
Input
2
3 5
5 3

Output
10
Input
2
5 3
3 5

Output
12


-----Note-----

 Explaination for the first sample [Image] t = 0

[Image] t = 2

[Image] t = 3

[Image] t = 5

[Image] t = 6

[Image] t = 7

[Image] t = 9

[Image] t = 10

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Little Petya loves presents. His mum bought him two strings of the same size for his birthday. The strings consist of uppercase and lowercase Latin letters. Now Petya wants to compare those two strings lexicographically. The letters' case does not matter, that is an uppercase letter is considered equivalent to the corresponding lowercase letter. Help Petya perform the comparison.

Input Specification:
Each of the first two lines contains a bought string. The strings' lengths range from 1 to 100 inclusive. It is guaranteed that the strings are of the same length and also consist of uppercase and lowercase Latin letters.

Output Specification:
If the first string is less than the second one, print "-1". If the second string is less than the first one, print "1". If the strings are equal, print "0". Note that the letters' case is not taken into consideration when the strings are compared.

Demo Input:
['aaaa\naaaA\n', 'abs\nAbz\n', 'abcdefg\nAbCdEfF\n']

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

Note:
If you want more formal information about the lexicographical order (also known as the "dictionary order" or "alphabetical order"), you can visit the following site:
-  http://en.wikipedia.org/wiki/Lexicographical_order

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tweedle-Dee and Tweedle-Dum are playing a fierce match of binary Nim. This novel game is played with $N$ stacks, each of them containing only $1$-s and $0$-s.
Just like in normal Nim, Tweedle-Dee and Tweedle-Dum alternate turns; in their turn, a player must choose one non-empty stack and remove a positive number of elements from the top of this stack. However, Tweedle-Dee may only choose a stack with $0$ at the top (and remove elements from it afterwards), and similarly, Tweedle-Dum may only choose a stack with $1$ at the top. the player that cannot make a move loses
Suzumo does not want to wait for the end of the game, so given the starting player he asks you to determine the winner. Remember that Tweedle-Dee and Tweedle-Dum are legendary grandmasters of combinatorial games, so both always play optimally.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains an integer $N$, a string $S$ denoting the number of stacks, the player that starts the game, respectively.
- Each of the following $N$ lines contains a single binary string $B$ representing a stack; the first character of $B$ corresponds to the top element of the stack and the last character to the bottom element.

-----Output-----
For each test case, print a single line containing the string "Dee" if Tweedle-Dee wins the match or "Dum" if Tweedle-Dum wins.

-----Constraints-----
- $1 \le T \le 500$
- $1 \le N \le 50$
- $1 \le |B| \le 50$
- each character in $B$ is either '1' or '0'
- $S$ is either "Dee" or "Dum"

-----Example Input-----
2
2 Dee
101
010
2 Dum
101
010

-----Example Output-----
Dum
Dee

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kira, is dreaming of building a new world, where all expressions will be special sequences. All these sequences consists of characters 'A','a','B','b','C','c'.

He devised the following rules:

An empty sequence is a valid sequence.

If Sequence1 is a special sequence, then so will be 'A' + Sequence1 + 'a', 'B' + Sequence1 + 'b', 'C' + Sequence1 + 'c'.
Example, let  Sequence1="", then Aa, Bb, Cc are also valid sequences.

If Sequence1 and Sequence2 are valid, then so is the sequence formed by concatenation of Sequence1 and Sequence2.

L (Kira's rival), has now replaced some characters with garbage from Kira's some of the favourite special sequences. Kira thinks he can add characters on his own to make then special again. You have to tell him number of special sequences that can be formed by replacing garbage characters with valid characters.

Input:

The first line contains N (it will be always even), the length of the sequence. Next line contains the string. Garbage characters in strings are denoted by '?'.

Output:

Print in one line the number of Special Sequences that can be formed by replacing '?' with valid characters.

Since this number could be huge, print this number modulo 100000.

Constraints:

2 ≤ N ≤ 200 

SAMPLE INPUT
10 
A?AC?ac?b?

SAMPLE OUTPUT
3

Explanation

The 3 special sequences are:

ABACAacaba

AaACAaCBbb

ACACcacBba

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have two strings, $a$ and $\boldsymbol{b}$. Find a string, $\boldsymbol{\mathrm{~S~}}$, such that:

$\boldsymbol{\mathrm{~S~}}$ can be expressed as $s=s_{a}+s_{b}$ where $\boldsymbol{s_{a}}$ is a non-empty substring of $a$ and $s_{b}$ is a non-empty substring of $\boldsymbol{b}$.
$\boldsymbol{\mathrm{~S~}}$ is a palindromic string.
The length of $\boldsymbol{\mathrm{~S~}}$ is as long as possible.

For each of the $\textit{q}$ pairs of strings ($a_i$ and $b_i$) received as input, find and print string $s_i$ on a new line. If you're able to form more than one valid string $s_i$, print whichever one comes first alphabetically. If there is no valid answer, print $-1$ instead.

Input Format

The first line contains a single integer, $\textit{q}$, denoting the number of queries. The subsequent lines describe each query over two lines:

The first line contains a single string denoting $\boldsymbol{a}$.
The second line contains a single string denoting $\boldsymbol{b}$.

Constraints

$1\leq q\leq10$  
$1\leq|a|,|b|\leq10^5$  
$\boldsymbol{\alpha}$ and $\boldsymbol{b}$ contain only lowercase English letters.
Sum of |a| over all queries does not exceed $2\times10^5$
Sum of |b| over all queries does not exceed $2\times10^5$

Output Format

For each pair of strings ($a_i$ and $b_i$), find some $s_i$ satisfying the conditions above and print it on a new line. If there is no such string, print $-1$ instead.

Sample Input
3
bac
bac
abc
def
jdfh
fds

Sample Output
aba
-1
dfhfd

Explanation

We perform the following three queries:

Concatenate $s_a=\textbf{"a"}$ with $s_b=\text{"ba''}$ to create $s=\text{"aba"}$.
We're given $a=\text{"abc"}$ and $s_a=\text{"def"}$; because both strings are composed of unique characters, we cannot use them to form a palindromic string. Thus, we print $-1$.
Concatenate $s_a=\text{"dfh"}$ with $s_b=\text{"fd“}$ to create $s=\text{"dfhfd"}$. Note that we chose these particular substrings because the length of string $\boldsymbol{\mathrm{~S~}}$ must be maximal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alex, Bob and Carl will soon participate in a team chess tournament. Since they are all in the same team, they have decided to practise really hard before the tournament. But it's a bit difficult for them because chess is a game for two players, not three.

So they play with each other according to following rules:  Alex and Bob play the first game, and Carl is spectating;  When the game ends, the one who lost the game becomes the spectator in the next game, and the one who was spectating plays against the winner. 

Alex, Bob and Carl play in such a way that there are no draws.

Today they have played n games, and for each of these games they remember who was the winner. They decided to make up a log of games describing who won each game. But now they doubt if the information in the log is correct, and they want to know if the situation described in the log they made up was possible (that is, no game is won by someone who is spectating if Alex, Bob and Carl play according to the rules). Help them to check it!


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 100) — the number of games Alex, Bob and Carl played.

Then n lines follow, describing the game log. i-th line contains one integer a_{i} (1 ≤ a_{i} ≤ 3) which is equal to 1 if Alex won i-th game, to 2 if Bob won i-th game and 3 if Carl won i-th game.


-----Output-----

Print YES if the situation described in the log was possible. Otherwise print NO.


-----Examples-----
Input
3
1
1
2

Output
YES

Input
2
1
2

Output
NO



-----Note-----

In the first example the possible situation is:  Alex wins, Carl starts playing instead of Bob;  Alex wins, Bob replaces Carl;  Bob wins. 

The situation in the second example is impossible because Bob loses the first game, so he cannot win the second one.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The only difference between easy and hard versions is the size of the input.

You are given a string $s$ consisting of $n$ characters, each character is 'R', 'G' or 'B'.

You are also given an integer $k$. Your task is to change the minimum number of characters in the initial string $s$ so that after the changes there will be a string of length $k$ that is a substring of $s$, and is also a substring of the infinite string "RGBRGBRGB ...".

A string $a$ is a substring of string $b$ if there exists a positive integer $i$ such that $a_1 = b_i$, $a_2 = b_{i + 1}$, $a_3 = b_{i + 2}$, ..., $a_{|a|} = b_{i + |a| - 1}$. For example, strings "GBRG", "B", "BR" are substrings of the infinite string "RGBRGBRGB ..." while "GR", "RGR" and "GGG" are not.

You have to answer $q$ independent queries.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries. Then $q$ queries follow.

The first line of the query contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the length of the string $s$ and the length of the substring.

The second line of the query contains a string $s$ consisting of $n$ characters 'R', 'G' and 'B'.

It is guaranteed that the sum of $n$ over all queries does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each query print one integer — the minimum number of characters you need to change in the initial string $s$ so that after changing there will be a substring of length $k$ in $s$ that is also a substring of the infinite string "RGBRGBRGB ...".


-----Example-----
Input
3
5 2
BGGGG
5 3
RBRGR
5 5
BBBRR

Output
1
0
3



-----Note-----

In the first example, you can change the first character to 'R' and obtain the substring "RG", or change the second character to 'R' and obtain "BR", or change the third, fourth or fifth character to 'B' and obtain "GB".

In the second example, the substring is "BRG".

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