vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: King's Path

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The black king is standing on a chess field consisting of 109 rows and 109 columns. We will consider the rows of the field numbered with integers from 1 to 109 from top to bottom. The columns are similarly numbered with integers from 1 to 109 from left to right. We will denote a cell of the field that is located in the *i*-th row and *j*-th column as (*i*,<=*j*).

You know that some squares of the given chess field are allowed. All allowed cells of the chess field are given as *n* segments. Each segment is described by three integers *r**i*,<=*a**i*,<=*b**i* (*a**i*<=≤<=*b**i*), denoting that cells in columns from number *a**i* to number *b**i* inclusive in the *r**i*-th row are allowed.

Your task is to find the minimum number of moves the king needs to get from square (*x*0,<=*y*0) to square (*x*1,<=*y*1), provided that he only moves along the allowed cells. In other words, the king can be located only on allowed cells on his way.

Let us remind you that a chess king can move to any of the neighboring cells in one move. Two cells of a chess field are considered neighboring if they share at least one point.

Input Specification:
The first line contains four space-separated integers *x*0,<=*y*0,<=*x*1,<=*y*1 (1<=≤<=*x*0,<=*y*0,<=*x*1,<=*y*1<=≤<=109), denoting the initial and the final positions of the king.

The second line contains a single integer *n* (1<=≤<=*n*<=≤<=105), denoting the number of segments of allowed cells. Next *n* lines contain the descriptions of these segments. The *i*-th line contains three space-separated integers *r**i*,<=*a**i*,<=*b**i* (1<=≤<=*r**i*,<=*a**i*,<=*b**i*<=≤<=109,<=*a**i*<=≤<=*b**i*), denoting that cells in columns from number *a**i* to number *b**i* inclusive in the *r**i*-th row are allowed. Note that the segments of the allowed cells can intersect and embed arbitrarily.

It is guaranteed that the king's initial and final position are allowed cells. It is guaranteed that the king's initial and the final positions do not coincide. It is guaranteed that the total length of all given segments doesn't exceed 105.

Output Specification:
If there is no path between the initial and final position along allowed cells, print -1.

Otherwise print a single integer — the minimum number of moves the king needs to get from the initial position to the final one.

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

Demo Output:
['4\n', '6\n', '-1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a positive integer n, find and return the longest distance between any two adjacent 1's in the binary representation of n. If there are no two adjacent 1's, return 0.
Two 1's are adjacent if there are only 0's separating them (possibly no 0's). The distance between two 1's is the absolute difference between their bit positions. For example, the two 1's in "1001" have a distance of 3.
 
Example 1:
Input: n = 22
Output: 2
Explanation: 22 in binary is "10110".
The first adjacent pair of 1's is "10110" with a distance of 2.
The second adjacent pair of 1's is "10110" with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.

Example 2:
Input: n = 5
Output: 2
Explanation: 5 in binary is "101".

Example 3:
Input: n = 6
Output: 1
Explanation: 6 in binary is "110".

Example 4:
Input: n = 8
Output: 0
Explanation: 8 in binary is "1000".
There aren't any adjacent pairs of 1's in the binary representation of 8, so we return 0.

Example 5:
Input: n = 1
Output: 0

 
Constraints:

1 <= n <= 109

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Thanks to the effects of El Nino this year my holiday snorkelling trip was akin to being in a washing machine... Not fun at all.

Given a string made up of '~' and '\_' representing waves and calm respectively, your job is to check whether a person would become seasick.

Remember, only the process of change from wave to calm (and vice versa) will add to the effect (really wave peak to trough but this will do). Find out how many changes in level the string has and if that figure is more than 20% of the string, return "Throw Up", if less, return "No Problem".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There was an electronic store heist last night.

All keyboards which were in the store yesterday were numbered in ascending order from some integer number $x$. For example, if $x = 4$ and there were $3$ keyboards in the store, then the devices had indices $4$, $5$ and $6$, and if $x = 10$ and there were $7$ of them then the keyboards had indices $10$, $11$, $12$, $13$, $14$, $15$ and $16$.

After the heist, only $n$ keyboards remain, and they have indices $a_1, a_2, \dots, a_n$. Calculate the minimum possible number of keyboards that have been stolen. The staff remember neither $x$ nor the number of keyboards in the store before the heist.


-----Input-----

The first line contains single integer $n$ $(1 \le n \le 1\,000)$ — the number of  keyboards in the store that remained after the heist.

The second line contains $n$ distinct integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^{9})$ — the indices of the remaining keyboards. The integers $a_i$ are given in arbitrary order and are pairwise distinct.


-----Output-----

Print the minimum possible number of keyboards that have been stolen if the staff remember neither $x$ nor the number of keyboards in the store before the heist.


-----Examples-----
Input
4
10 13 12 8

Output
2

Input
5
7 5 6 4 8

Output
0



-----Note-----

In the first example, if $x=8$ then minimum number of stolen keyboards is equal to $2$. The keyboards with indices $9$ and $11$ were stolen during the heist.

In the second example, if $x=4$ then nothing was stolen during the heist.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Jamie and Alarm Snooze

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Jamie loves sleeping. One day, he decides that he needs to wake up at exactly *hh*:<=*mm*. However, he hates waking up, so he wants to make waking up less painful by setting the alarm at a lucky time. He will then press the snooze button every *x* minutes until *hh*:<=*mm* is reached, and only then he will wake up. He wants to know what is the smallest number of times he needs to press the snooze button.

A time is considered lucky if it contains a digit '7'. For example, 13:<=07 and 17:<=27 are lucky, while 00:<=48 and 21:<=34 are not lucky.

Note that it is not necessary that the time set for the alarm and the wake-up time are on the same day. It is guaranteed that there is a lucky time Jamie can set so that he can wake at *hh*:<=*mm*.

Formally, find the smallest possible non-negative integer *y* such that the time representation of the time *x*·*y* minutes before *hh*:<=*mm* contains the digit '7'.

Jamie uses 24-hours clock, so after 23:<=59 comes 00:<=00.

Input Specification:
The first line contains a single integer *x* (1<=≤<=*x*<=≤<=60).

The second line contains two two-digit integers, *hh* and *mm* (00<=≤<=*hh*<=≤<=23,<=00<=≤<=*mm*<=≤<=59).

Output Specification:
Print the minimum number of times he needs to press the button.

Demo Input:
['3\n11 23\n', '5\n01 07\n']

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

Note:
In the first sample, Jamie needs to wake up at 11:23. So, he can set his alarm at 11:17. He would press the snooze button when the alarm rings at 11:17 and at 11:20.

In the second sample, Jamie can set his alarm at exactly at 01:07 which is lucky.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The International Corporation for Protection and Control (ICPC) develops efficient technology for, well, protection and control. Naturally, they are keen to have their own headquarters protected and controlled. Viewed from above, the headquarters building has the shape of a convex polygon. There are several suitable places around it where cameras can be installed to monitor the building. Each camera covers a certain range of the polygon sides (building walls), depending on its position. ICPC wants to minimize the number of cameras needed to cover the whole building.

-----Input-----
The input consists of a single test case. Its first line contains two integers $n$ and $k$ ($3 \le n \le 10^6$ and $1 \le k \le 10^6$), where $n$ is the number of walls and $k$ is the number of possible places for installing cameras. Each of the remaining $k$ lines contains two integers $a_ i$ and $b_ i$ ($1 \le a_ i, b_ i \le n$). These integers specify which walls a camera at the $i^{th}$ place would cover. If $a_ i \le b_ i$ then the camera covers each wall $j$ such that $a_ i \le j \le b_ i$. If $a_ i > b_ i$ then the camera covers each wall $j$ such that $a_ i \le j \le n$ or $1 \le j \le b_ i$.

-----Output-----
Display the minimal number of cameras that suffice to cover each wall of the building. The ranges covered by two cameras may overlap. If the building cannot be covered, display impossible instead.

-----Examples-----
Sample Input 1:
100 7
1 50
50 70
70 90
90 40
20 60
60 80
80 20
Sample Output 1:
3

Sample Input 2:
8 2
8 3
5 7
Sample Output 2:
impossible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given $n$ strings $a_1, a_2, \ldots, a_n$: all of them have the same length $m$. The strings consist of lowercase English letters.

Find any string $s$ of length $m$ such that each of the given $n$ strings differs from $s$ in at most one position. Formally, for each given string $a_i$, there is no more than one position $j$ such that $a_i[j] \ne s[j]$.

Note that the desired string $s$ may be equal to one of the given strings $a_i$, or it may differ from all the given strings.

For example, if you have the strings abac and zbab, then the answer to the problem might be the string abab, which differs from the first only by the last character, and from the second only by the first.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 100$) — the number of test cases. Then $t$ test cases follow.

Each test case starts with a line containing two positive integers $n$ ($1 \le n \le 10$) and $m$ ($1 \le m \le 10$) — the number of strings and their length.

Then follow $n$ strings $a_i$, one per line. Each of them has length $m$ and consists of lowercase English letters.


-----Output-----

Print $t$ answers to the test cases. Each answer (if it exists) is a string of length $m$ consisting of lowercase English letters. If there are several answers, print any of them. If the answer does not exist, print "-1" ("minus one", without quotes).


-----Example-----
Input
5
2 4
abac
zbab
2 4
aaaa
bbbb
3 3
baa
aaa
aab
2 2
ab
bb
3 1
a
b
c

Output
abab
-1
aaa
ab
z


-----Note-----

The first test case was explained in the statement.

In the second test case, the answer does not exist.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The prison of your city has *n* prisoners. As the prison can't accommodate all of them, the city mayor has decided to transfer *c* of the prisoners to a prison located in another city.

For this reason, he made the *n* prisoners to stand in a line, with a number written on their chests. The number is the severity of the crime he/she has committed. The greater the number, the more severe his/her crime was.

Then, the mayor told you to choose the *c* prisoners, who will be transferred to the other prison. He also imposed two conditions. They are,
 -  The chosen *c* prisoners has to form a contiguous segment of prisoners. -  Any of the chosen prisoner's crime level should not be greater then *t*. Because, that will make the prisoner a severe criminal and the mayor doesn't want to take the risk of his running away during the transfer. 
Find the number of ways you can choose the *c* prisoners.

Input Specification:
The first line of input will contain three space separated integers *n* (1<=≤<=*n*<=≤<=2·105), *t* (0<=≤<=*t*<=≤<=109) and *c* (1<=≤<=*c*<=≤<=*n*). The next line will contain *n* space separated integers, the *i**th* integer is the severity *i**th* prisoner's crime. The value of crime severities will be non-negative and will not exceed 109.

Output Specification:
Print a single integer — the number of ways you can choose the *c* prisoners.

Demo Input:
['4 3 3\n2 3 1 1\n', '1 1 1\n2\n', '11 4 2\n2 2 0 7 3 2 2 4 9 1 4\n']

Demo Output:
['2\n', '0\n', '6\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let $n$ be a positive integer. Let $a, b, c$ be nonnegative integers such that $a + b + c = n$.

Alice and Bob are gonna play rock-paper-scissors $n$ times. Alice knows the sequences of hands that Bob will play. However, Alice has to play rock $a$ times, paper $b$ times, and scissors $c$ times.

Alice wins if she beats Bob in at least $\lceil \frac{n}{2} \rceil$ ($\frac{n}{2}$ rounded up to the nearest integer) hands, otherwise Alice loses.

Note that in rock-paper-scissors:

  rock beats scissors;  paper beats rock;  scissors beat paper. 

The task is, given the sequence of hands that Bob will play, and the numbers $a, b, c$, determine whether or not Alice can win. And if so, find any possible sequence of hands that Alice can use to win.

If there are multiple answers, print any of them.


-----Input-----

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

Then, $t$ testcases follow, each consisting of three lines:   The first line contains a single integer $n$ ($1 \le n \le 100$).  The second line contains three integers, $a, b, c$ ($0 \le a, b, c \le n$). It is guaranteed that $a + b + c = n$.  The third line contains a string $s$ of length $n$. $s$ is made up of only 'R', 'P', and 'S'. The $i$-th character is 'R' if for his $i$-th Bob plays rock, 'P' if paper, and 'S' if scissors. 


-----Output-----

For each testcase:   If Alice cannot win, print "NO" (without the quotes).  Otherwise, print "YES" (without the quotes). Also, print a string $t$ of length $n$ made up of only 'R', 'P', and 'S' — a sequence of hands that Alice can use to win. $t$ must contain exactly $a$ 'R's, $b$ 'P's, and $c$ 'S's.  If there are multiple answers, print any of them. 

The "YES" / "NO" part of the output is case-insensitive (i.e. "yEs", "no" or "YEs" are all valid answers). Note that 'R', 'P' and 'S' are case-sensitive.


-----Example-----
Input
2
3
1 1 1
RPS
3
3 0 0
RPS

Output
YES
PSR
NO



-----Note-----

In the first testcase, in the first hand, Alice plays paper and Bob plays rock, so Alice beats Bob. In the second hand, Alice plays scissors and Bob plays paper, so Alice beats Bob. In the third hand, Alice plays rock and Bob plays scissors, so Alice beats Bob. Alice beat Bob 3 times, and $3 \ge \lceil \frac{3}{2} \rceil = 2$, so Alice wins.

In the second testcase, the only sequence of hands that Alice can play is "RRR". Alice beats Bob only in the last hand, so Alice can't win. $1 < \lceil \frac{3}{2} \rceil = 2$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a non-empty string *s* consisting of lowercase English letters. You have to pick exactly one non-empty substring of *s* and shift all its letters 'z'  'y'  'x'  'b'  'a'  'z'. In other words, each character is replaced with the previous character of English alphabet and 'a' is replaced with 'z'.

What is the lexicographically minimum string that can be obtained from *s* by performing this shift exactly once?

Input Specification:
The only line of the input contains the string *s* (1<=≤<=|*s*|<=≤<=100<=000) consisting of lowercase English letters.

Output Specification:
Print the lexicographically minimum string that can be obtained from *s* by shifting letters of exactly one non-empty substring.

Demo Input:
['codeforces\n', 'abacaba\n']

Demo Output:
['bncdenqbdr\n', 'aaacaba\n']

Note:
String *s* is lexicographically smaller than some other string *t* of the same length if there exists some 1 ≤ *i* ≤ |*s*|, such that *s*<sub class="lower-index">1</sub> = *t*<sub class="lower-index">1</sub>, *s*<sub class="lower-index">2</sub> = *t*<sub class="lower-index">2</sub>, ..., *s*<sub class="lower-index">*i* - 1</sub> = *t*<sub class="lower-index">*i* - 1</sub>, and *s*<sub class="lower-index">*i*</sub> &lt; *t*<sub class="lower-index">*i*</sub>.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n students in a school class, the rating of the i-th student on Codehorses is a_i. You have to form a team consisting of k students (1 ≤ k ≤ n) such that the ratings of all team members are distinct.

If it is impossible to form a suitable team, print "NO" (without quotes). Otherwise print "YES", and then print k distinct numbers which should be the indices of students in the team you form. If there are multiple answers, print any of them.

Input

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 100) — the number of students and the size of the team you have to form.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 100), where a_i is the rating of i-th student.

Output

If it is impossible to form a suitable team, print "NO" (without quotes). Otherwise print "YES", and then print k distinct integers from 1 to n which should be the indices of students in the team you form. All the ratings of the students in the team should be distinct. You may print the indices in any order. If there are multiple answers, print any of them.

Assume that the students are numbered from 1 to n.

Examples

Input

5 3
15 13 15 15 12


Output

YES
1 2 5 


Input

5 4
15 13 15 15 12


Output

NO


Input

4 4
20 10 40 30


Output

YES
1 2 3 4 

Note

All possible answers for the first example: 

  * {1 2 5} 
  * {2 3 5} 
  * {2 4 5} 



Note that the order does not matter.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Fifa and Fafa are sharing a flat. Fifa loves video games and wants to download a new soccer game. Unfortunately, Fafa heavily uses the internet which consumes the quota. Fifa can access the internet through his Wi-Fi access point. This access point can be accessed within a range of *r* meters (this range can be chosen by Fifa) from its position. Fifa must put the access point inside the flat which has a circular shape of radius *R*. Fifa wants to minimize the area that is not covered by the access point inside the flat without letting Fafa or anyone outside the flat to get access to the internet.

The world is represented as an infinite 2D plane. The flat is centered at (*x*1,<=*y*1) and has radius *R* and Fafa's laptop is located at (*x*2,<=*y*2), not necessarily inside the flat. Find the position and the radius chosen by Fifa for his access point which minimizes the uncovered area.

Input Specification:
The single line of the input contains 5 space-separated integers *R*,<=*x*1,<=*y*1,<=*x*2,<=*y*2 (1<=≤<=*R*<=≤<=105, |*x*1|,<=|*y*1|,<=|*x*2|,<=|*y*2|<=≤<=105).

Output Specification:
Print three space-separated numbers *x**ap*,<=*y**ap*,<=*r* where (*x**ap*,<=*y**ap*) is the position which Fifa chose for the access point and *r* is the radius of its range. 

Your answer will be considered correct if the radius does not differ from optimal more than 10<=-<=6 absolutely or relatively, and also the radius you printed can be changed by no more than 10<=-<=6 (absolutely or relatively) in such a way that all points outside the flat and Fafa's laptop position are outside circle of the access point range.

Demo Input:
['5 3 3 1 1\n', '10 5 5 5 15\n']

Demo Output:
['3.7677669529663684 3.7677669529663684 3.914213562373095\n', '5.0 5.0 10.0\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
At regular competition Vladik and Valera won a and b candies respectively. Vladik offered 1 his candy to Valera. After that Valera gave Vladik 2 his candies, so that no one thought that he was less generous. Vladik for same reason gave 3 candies to Valera in next turn.

More formally, the guys take turns giving each other one candy more than they received in the previous turn.

This continued until the moment when one of them couldn’t give the right amount of candy. Candies, which guys got from each other, they don’t consider as their own. You need to know, who is the first who can’t give the right amount of candy.


-----Input-----

Single line of input data contains two space-separated integers a, b (1 ≤ a, b ≤ 10^9) — number of Vladik and Valera candies respectively.


-----Output-----

Pring a single line "Vladik’’ in case, if Vladik first who can’t give right amount of candy, or "Valera’’ otherwise.


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

Output
Valera

Input
7 6

Output
Vladik



-----Note-----

Illustration for first test case:

[Image]

Illustration for second test case:

[Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Number encrypting: cypher
## Part I of Number encrypting Katas
***

## Introduction
Back then when the internet was coming up, most search functionalities simply looked for keywords in text to show relevant documents. Hackers weren't very keen on having their information displayed on websites, bulletin boards, newsgroups or any other place, so they started to replace certain letters in words. It started out with simple vowel substitutions like a 4 instead of an A, or a 3 instead of an E. This meant that topics like cracking or hacking remained undetected.

Here we will use a reduced version of the *Leet Speak alphabet*, but you can find more information [here](http://www.gamehouse.com/blog/leet-speak-cheat-sheet/) or at [Wikipedia](https://en.wikipedia.org/wiki/Leet).

## Task
You will receive a string composed by English words, `string`. You will have to return a cyphered version of that string.

The numbers corresponding to each letter are represented at the table below. Notice that different letters can share the same number. In those cases, one letter will be upper case and the other one lower case.


  .cell {
    border: 1px solid white;
    text-align: center;
    width: 7%;
  }
  
  .title {
    border: 1px solid white;
    border-bottom: 1px solid white;
    text-align: center;
    min-width: 11em;
  }
  
  .no-border {border: none}
  
  table {
    margin-bottom: 10px
  }



  
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    0
  
  
    Upper case
    I
    R
    E
    A
    S
    G
    T
    B
    
    O
  
  
    Lower case
    l
    z
    e
    a
    s
    b
    t
    
    g
    o
  
  



Any character that is not at the table, does not change when cyphered.

## Examples

  * **Input:** "Hello World". **Output**: "H3110 W0r1d"
  * **Input:** "I am your father". **Output**: "1 4m y0ur f47h3r"
  * **Input:** "I do not know what else I can test. Be cool. Good luck". **Output**: "1 d0 n07 kn0w wh47 3153 1 c4n 7357. 83 c001. 600d 1uck"

## Part II
If you liked this Kata, you can find the [part II: *Number encrypting: decypher*](https://www.codewars.com/kata/number-encrypting-decypher), where your goal is to decypher the strings.

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