vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Jim has invented a new flying object called HZ42. HZ42 is like a broom and can only fly horizontally, independent of the environment. One day, Jim started his flight from Dubai's highest skyscraper, traveled some distance and landed on another skyscraper of same height! So much fun! But unfortunately, new skyscrapers have been built recently.

Let us describe the problem in one dimensional space. We have in total $N$ skyscrapers aligned from left to right. The $\boldsymbol{i}$^{th} skyscraper has a height of $h_i$. A flying route can be described as $(i,j)$ with $i\neq j$, which means, Jim starts his HZ42 at the top of the skyscraper $\boldsymbol{i}$ and lands on the skyscraper $j$. Since HZ42 can only fly horizontally, Jim will remain at the height $h_i$ only. Thus the path $(i,j)$ can be valid, only if each of the skyscrapers $i,i+1,\ldots,j-1,j$ is not strictly greater than $h_i$ and if the height of the skyscraper he starts from and arrives on have the same height. Formally, $(i,j)$ is valid iff $\nexists k\in[i,j]:h_k>h_i$ and $h_i=h_j$.

Help Jim in counting the number of valid paths represented by ordered pairs $(i,j)$.  

Input Format

The first line contains $N$, the number of skyscrapers. The next line contains $N$ space separated integers representing the heights of the skyscrapers. 

Output Format

Print an integer that denotes the number of valid routes.

Constraints

$1\leq N\leq3\cdot10^5$ and no skyscraper will have height greater than $10^{6}$ and less than $\mbox{1}$.

Sample Input #00

6
3 2 1 2 3 3

Sample Output #00

8

Sample Input #01

3
1 1000 1

Sample Output #01

0

Explanation

First testcase: (1, 5), (1, 6) (5, 6) and (2, 4) and the routes in the opposite directions are the only valid routes. 

Second testcase: (1, 3) and (3, 1) could have been valid, if there wasn't a big skyscraper with height 1000 between them.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Arthur has bought a beautiful big table into his new flat. When he came home, Arthur noticed that the new table is unstable.

In total the table Arthur bought has *n* legs, the length of the *i*-th leg is *l**i*.

Arthur decided to make the table stable and remove some legs. For each of them Arthur determined number *d**i* — the amount of energy that he spends to remove the *i*-th leg.

A table with *k* legs is assumed to be stable if there are more than half legs of the maximum length. For example, to make a table with 5 legs stable, you need to make sure it has at least three (out of these five) legs of the maximum length. Also, a table with one leg is always stable and a table with two legs is stable if and only if they have the same lengths.

Your task is to help Arthur and count the minimum number of energy units Arthur should spend on making the table stable.

Input Specification:
The first line of the input contains integer *n* (1<=≤<=*n*<=≤<=105) — the initial number of legs in the table Arthur bought.

The second line of the input contains a sequence of *n* integers *l**i* (1<=≤<=*l**i*<=≤<=105), where *l**i* is equal to the length of the *i*-th leg of the table.

The third line of the input contains a sequence of *n* integers *d**i* (1<=≤<=*d**i*<=≤<=200), where *d**i* is the number of energy units that Arthur spends on removing the *i*-th leg off the table.

Output Specification:
Print a single integer — the minimum number of energy units that Arthur needs to spend in order to make the table stable.

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

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jeff's got n cards, each card contains either digit 0, or digit 5. Jeff can choose several cards and put them in a line so that he gets some number. What is the largest possible number divisible by 90 Jeff can make from the cards he's got?

Jeff must make the number without leading zero. At that, we assume that number 0 doesn't contain any leading zeroes. Jeff doesn't have to use all the cards.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^3). The next line contains n integers a_1, a_2, ..., a_{n} (a_{i} = 0 or a_{i} = 5). Number a_{i} represents the digit that is written on the i-th card.


-----Output-----

In a single line print the answer to the problem — the maximum number, divisible by 90. If you can't make any divisible by 90 number from the cards, print -1.


-----Examples-----
Input
4
5 0 5 0

Output
0

Input
11
5 5 5 5 5 5 5 5 0 5 5

Output
5555555550



-----Note-----

In the first test you can make only one number that is a multiple of 90 — 0.

In the second test you can make number 5555555550, it is a multiple of 90.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bimokh is Mashmokh's boss. For the following n days he decided to pay to his workers in a new way. At the beginning of each day he will give each worker a certain amount of tokens. Then at the end of each day each worker can give some of his tokens back to get a certain amount of money. The worker can save the rest of tokens but he can't use it in any other day to get more money. If a worker gives back w tokens then he'll get $\lfloor \frac{w \cdot a}{b} \rfloor$ dollars. 

Mashmokh likes the tokens however he likes money more. That's why he wants to save as many tokens as possible so that the amount of money he gets is maximal possible each day. He has n numbers x_1, x_2, ..., x_{n}. Number x_{i} is the number of tokens given to each worker on the i-th day. Help him calculate for each of n days the number of tokens he can save.


-----Input-----

The first line of input contains three space-separated integers n, a, b (1 ≤ n ≤ 10^5; 1 ≤ a, b ≤ 10^9). The second line of input contains n space-separated integers x_1, x_2, ..., x_{n} (1 ≤ x_{i} ≤ 10^9).


-----Output-----

Output n space-separated integers. The i-th of them is the number of tokens Mashmokh can save on the i-th day.


-----Examples-----
Input
5 1 4
12 6 11 9 1

Output
0 2 3 1 1 
Input
3 1 2
1 2 3

Output
1 0 1 
Input
1 1 1
1

Output
0

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The Free Meteor Association (FMA) has got a problem: as meteors are moving, the Universal Cosmic Descriptive Humorous Program (UCDHP) needs to add a special module that would analyze this movement. 

UCDHP stores some secret information about meteors as an *n*<=×<=*m* table with integers in its cells. The order of meteors in the Universe is changing. That's why the main UCDHP module receives the following queries:
 -  The query to swap two table rows; -  The query to swap two table columns; -  The query to obtain a secret number in a particular table cell. 
As the main UCDHP module is critical, writing the functional of working with the table has been commissioned to you.

Input Specification:
The first line contains three space-separated integers *n*, *m* and *k* (1<=≤<=*n*,<=*m*<=≤<=1000, 1<=≤<=*k*<=≤<=500000) — the number of table columns and rows and the number of queries, correspondingly.

Next *n* lines contain *m* space-separated numbers each — the initial state of the table. Each number *p* in the table is an integer and satisfies the inequality 0<=≤<=*p*<=≤<=106.

Next *k* lines contain queries in the format "*s**i* *x**i* *y**i*", where *s**i* is one of the characters "с", "r" or "g", and *x**i*, *y**i* are two integers.
 -  If *s**i* = "c", then the current query is the query to swap columns with indexes *x**i* and *y**i* (1<=≤<=*x*,<=*y*<=≤<=*m*,<=*x*<=≠<=*y*); -  If *s**i* = "r", then the current query is the query to swap rows with indexes *x**i* and *y**i* (1<=≤<=*x*,<=*y*<=≤<=*n*,<=*x*<=≠<=*y*); -  If *s**i* = "g", then the current query is the query to obtain the number that located in the *x**i*-th row and in the *y**i*-th column (1<=≤<=*x*<=≤<=*n*,<=1<=≤<=*y*<=≤<=*m*). 
The table rows are considered to be indexed from top to bottom from 1 to *n*, and the table columns — from left to right from 1 to *m*.

Output Specification:
For each query to obtain a number (*s**i* = "g") print the required number. Print the answers to the queries in the order of the queries in the input.

Demo Input:
['3 3 5\n1 2 3\n4 5 6\n7 8 9\ng 3 2\nr 3 2\nc 2 3\ng 2 2\ng 3 2\n', '2 3 3\n1 2 4\n3 1 5\nc 2 1\nr 1 2\ng 1 3\n']

Demo Output:
['8\n9\n6\n', '5\n']

Note:
Let's see how the table changes in the second test case.

After the first operation is fulfilled, the table looks like that:

2 1 4

1 3 5

After the second operation is fulfilled, the table looks like that:

1 3 5

2 1 4

So the answer to the third query (the number located in the first row and in the third column) will be 5.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
In the lattice points of the coordinate line there are *n* radio stations, the *i*-th of which is described by three integers:
 -  *x**i* — the coordinate of the *i*-th station on the line, -  *r**i* — the broadcasting range of the *i*-th station, -  *f**i* — the broadcasting frequency of the *i*-th station. 
We will say that two radio stations with numbers *i* and *j* reach each other, if the broadcasting range of each of them is more or equal to the distance between them. In other words *min*(*r**i*,<=*r**j*)<=≥<=|*x**i*<=-<=*x**j*|.

Let's call a pair of radio stations (*i*,<=*j*) bad if *i*<=&lt;<=*j*, stations *i* and *j* reach each other and they are close in frequency, that is, |*f**i*<=-<=*f**j*|<=≤<=*k*.

Find the number of bad pairs of radio stations.

Input Specification:
The first line contains two integers *n* and *k* (1<=≤<=*n*<=≤<=105, 0<=≤<=*k*<=≤<=10) — the number of radio stations and the maximum difference in the frequencies for the pair of stations that reach each other to be considered bad.

In the next *n* lines follow the descriptions of radio stations. Each line contains three integers *x**i*, *r**i* and *f**i* (1<=≤<=*x**i*,<=*r**i*<=≤<=109, 1<=≤<=*f**i*<=≤<=104) — the coordinate of the *i*-th radio station, it's broadcasting range and it's broadcasting frequency. No two radio stations will share a coordinate.

Output Specification:
Output the number of bad pairs of radio stations.

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

Demo Output:
['1\n', '2\n', '2\n', '5\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Amugae is in a very large round corridor. The corridor consists of two areas. The inner area is equally divided by n sectors, and the outer area is equally divided by m sectors. A wall exists between each pair of sectors of same area (inner or outer), but there is no wall between the inner area and the outer area. A wall always exists at the 12 o'clock position.

<image>

The inner area's sectors are denoted as (1,1), (1,2), ..., (1,n) in clockwise direction. The outer area's sectors are denoted as (2,1), (2,2), ..., (2,m) in the same manner. For a clear understanding, see the example image above.

Amugae wants to know if he can move from one sector to another sector. He has q questions.

For each question, check if he can move between two given sectors.

Input

The first line contains three integers n, m and q (1 ≤ n, m ≤ 10^{18}, 1 ≤ q ≤ 10^4) — the number of sectors in the inner area, the number of sectors in the outer area and the number of questions.

Each of the next q lines contains four integers s_x, s_y, e_x, e_y (1 ≤ s_x, e_x ≤ 2; if s_x = 1, then 1 ≤ s_y ≤ n, otherwise 1 ≤ s_y ≤ m; constraints on e_y are similar). Amague wants to know if it is possible to move from sector (s_x, s_y) to sector (e_x, e_y).

Output

For each question, print "YES" if Amugae can move from (s_x, s_y) to (e_x, e_y), and "NO" otherwise.

You can print each letter in any case (upper or lower).

Example

Input


4 6 3
1 1 2 3
2 6 1 2
2 6 2 4


Output


YES
NO
YES

Note

Example is shown on the picture in the statement.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Three infinite lines define a triangle, unless they meet at a common point or some of them are parallel.

Given a collection of infinite lines, what is the largest possible perimeter of a triangle defined by some three lines in the collection?

-----Input-----
The first line of input contains a single integer $n$ ($3 \leq n \leq 100$) indicating the number of infinite lines.

The next $n$ lines describe the collection of infinite lines. The $i^{\textrm{th}}$ such line contains four integers $x_1, y_1, x_2, y_2$ ($-10000 \leq x_1, y_1, x_2, y_2 \leq 10000$) where $(x_1, y_1) \neq (x_2, y_2)$ are two points lying on the $i^{\textrm{th}}$ infinite line.

-----Output-----
Display a single real value which is the perimeter of the largest triangle that can be formed from three of the infinite lines. Your output will be considered correct if it is within an absolute or relative error of $10^{-5}$ of the correct answer.

If no triangle can be formed using the given lines, then you should instead display the message no triangle.

-----Examples-----
Sample Input 1:
3
0 0 0 1
0 0 1 0
0 1 1 0
Sample Output 1:
3.4142135624

Sample Input 2:
3
0 0 0 1
0 0 1 0
0 0 1 1
Sample Output 2:
no triangle

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your goal is to create a function to format a number given a template; if the number is not present, use the digits `1234567890` to fill in the spaces.

A few rules:

* the template might consist of other numbers, special characters or the like: you need to replace only alphabetical characters (both lower- and uppercase);
* if the given or default string representing the number is shorter than the template, just repeat it to fill all the spaces.

A few examples:

```python
numeric_formatter("xxx xxxxx xx","5465253289") == "546 52532 89"
numeric_formatter("xxx xxxxx xx") == "123 45678 90"
numeric_formatter("+555 aaaa bbbb", "18031978") == "+555 1803 1978"
numeric_formatter("+555 aaaa bbbb") == "+555 1234 5678"
numeric_formatter("xxxx yyyy zzzz") == "1234 5678 9012"
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the i-th round, you toggle every i bulb. For the n-th round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:


Input: 3
Output: 1 
Explanation: 
At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off]. 

So you should return 1, because there is only one bulb is on.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice and Bob play a game. They have a binary string $s$ (a string such that each character in it is either $0$ or $1$). Alice moves first, then Bob, then Alice again, and so on.

During their move, the player can choose any number (not less than one) of consecutive equal characters in $s$ and delete them.

For example, if the string is $10110$, there are $6$ possible moves (deleted characters are bold):  $\textbf{1}0110 \to 0110$;  $1\textbf{0}110 \to 1110$;  $10\textbf{1}10 \to 1010$;  $101\textbf{1}0 \to 1010$;  $10\textbf{11}0 \to 100$;  $1011\textbf{0} \to 1011$. 

After the characters are removed, the characters to the left and to the right of the removed block become adjacent. I. e. the following sequence of moves is valid: $10\textbf{11}0 \to 1\textbf{00} \to 1$.

The game ends when the string becomes empty, and the score of each player is the number of $1$-characters deleted by them.

Each player wants to maximize their score. Calculate the resulting score of Alice.


-----Input-----

The first line contains one integer $T$ ($1 \le T \le 500$) — the number of test cases.

Each test case contains exactly one line containing a binary string $s$ ($1 \le |s| \le 100$).


-----Output-----

For each test case, print one integer — the resulting score of Alice (the number of $1$-characters deleted by her).


-----Example-----
Input
5
01111001
0000
111111
101010101
011011110111

Output
4
0
6
3
6



-----Note-----

Questions about the optimal strategy will be ignored.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Iahub and his friend Floyd have started painting a wall. Iahub is painting the wall red and Floyd is painting it pink. You can consider the wall being made of a very large number of bricks, numbered 1, 2, 3 and so on. 

Iahub has the following scheme of painting: he skips x - 1 consecutive bricks, then he paints the x-th one. That is, he'll paint bricks x, 2·x, 3·x and so on red. Similarly, Floyd skips y - 1 consecutive bricks, then he paints the y-th one. Hence he'll paint bricks y, 2·y, 3·y and so on pink.

After painting the wall all day, the boys observed that some bricks are painted both red and pink. Iahub has a lucky number a and Floyd has a lucky number b. Boys wonder how many bricks numbered no less than a and no greater than b are painted both red and pink. This is exactly your task: compute and print the answer to the question. 

Input

The input will have a single line containing four integers in this order: x, y, a, b. (1 ≤ x, y ≤ 1000, 1 ≤ a, b ≤ 2·109, a ≤ b).

Output

Output a single integer — the number of bricks numbered no less than a and no greater than b that are painted both red and pink.

Examples

Input

2 3 6 18


Output

3

Note

Let's look at the bricks from a to b (a = 6, b = 18). The bricks colored in red are numbered 6, 8, 10, 12, 14, 16, 18. The bricks colored in pink are numbered 6, 9, 12, 15, 18. The bricks colored in both red and pink are numbered with 6, 12 and 18. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Maya writes weekly articles to a well known magazine, but she is missing one word each time she is about to send the article to the editor. The article is not complete without this word. Maya has a friend, Dan, and he is very good with words, but he doesn't like to just give them away. He texts Maya a number and she needs to find out the hidden word. 
The words can contain only the letter: "a", "b", "d", "e", "i", "l", "m", "n", "o", and "t".

Luckily, Maya has the key:

"a" - 6
"b" - 1 
"d" - 7
"e" - 4
"i" - 3
"l" - 2
"m" - 9
"n" - 8
"o" - 0
"t" - 5

You can help Maya by writing a function that will take a number between 100 and 999999 and return a string with the word. 

The input is always a number, contains only the numbers in the key. 
The output should be always a string with one word, all lowercase.

Maya won't forget to thank you at the end of her article :)

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

There is a rectangular piece of paper divided in a grid with a height of $ H $ squares and a width of $ W $ squares. The integer $ i \ times W + j $ is written in the cell of the $ i $ line from the top and the $ j $ column from the left counting from $ 0 $. An example of $ H = 2 and W = 3 $ is shown in the figure below.

<image>

AOR Ika-chan performed the following operations on this paper in order.

1. Fold it repeatedly along the dividing line of the square until it reaches the area of ​​$ 1 $ square. The folding lines, mountains and valleys, and the order at this time are arbitrary. You can fold it in any way that does not tear the paper.
2. Cut off the $ 4 $ edge and divide it into $ H \ times W $ sheets of paper.
3. Turn over from the top to create a sequence $ S $ in which the written integers are arranged.



For example, if you fold it and then cut it as shown in the figure below, you will get $ 4, 3, 0, 5, 2, 1 $ as $ S $. In this way, it is possible to fold it so that it can be inserted between them.

<image>
<image>

You received a sequence of $ S $ from AOR Ika-chan. However, I don't trust AOR Ika-chan, so I want to make sure this is the real thing. Write a program that outputs "YES" if there is a paper folding method that matches $ S $, and "NO" if not.

Input constraints

$ 1 \ le H, W \ le 500 $
$ S $ contains integers from $ 0 $ to $ H \ times W --1 $ in increments of $ 1 $

sample

Sample input 1


14
0 1 2 3


Sample output 1


YES YES


<image>

Sample input 2


twenty three
4 3 0 5 2 1


Sample output 2


YES YES


This is an example in the problem statement.

Sample input 3


14
0 2 1 3


Sample output 3


NO


Sample input 4


twenty two
0 1 3 2


Sample output 4


YES YES


Fold it in half for $ 2 $.



input

$ H \ W $
$ S_0 \ cdots S_ {HW-1} $

output

Print "YES" or "NO" on the $ 1 $ line.

Example

Input

1 4
0 1 2 3


Output

YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A positive integer X is said to be a lunlun number if and only if the following condition is satisfied:
 - In the base ten representation of X (without leading zeros), for every pair of two adjacent digits, the absolute difference of those digits is at most 1.
For example, 1234, 1, and 334 are lunlun numbers, while none of 31415, 119, or 13579 is.
You are given a positive integer K. Find the K-th smallest lunlun number.

-----Constraints-----
 - 1 \leq K \leq 10^5
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
K

-----Output-----
Print the answer.

-----Sample Input-----
15

-----Sample Output-----
23

We will list the 15 smallest lunlun numbers in ascending order:
1,
2,
3,
4,
5,
6,
7,
8,
9,
10,
11,
12,
21,
22,
23.

Thus, the answer is 23.

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

*You're saying good-bye your best friend* , **_See you next happy year_** . 

**_Happy Year_** *is the year with only distinct digits* , (e.g) **_2018_**

___
# Task

**_Given_** a year, **_Find_** **_The next happy year_** or **_The closest year You'll see your best friend_**      ![!alt](https://i.imgur.com/mdX8dJP.png) ![!alt](https://i.imgur.com/mdX8dJP.png)

___
# Notes

* **_Year_** Of Course always **_Positive_** .
* **_Have no fear_** , *It is guaranteed that the answer exists* . 
* **_It's not necessary_** *that the year passed to the function is Happy one* .   
* **_Input Year with in range_** *(1000  ≤  y  ≤  9000)*

____
# Input >> Output Examples:

```
nextHappyYear (7712) ==> return (7801)
```

## **_Explanation_**:

As the **_Next closest year with only distinct digits is_**  *7801* . 
___

```
nextHappyYear (8989) ==> return (9012)
```

## **_Explanation_**:

As the **_Next closest year with only distinct digits is_**  *9012* . 
___

```
nextHappyYear (1001) ==> return (1023)
```

## **_Explanation_**:

As the **_Next closest year with only distinct digits is_**  *1023* .
___
___
___

# [Playing with Numbers Series](https://www.codewars.com/collections/playing-with-numbers)

# [Playing With Lists/Arrays Series](https://www.codewars.com/collections/playing-with-lists-slash-arrays)

# [For More Enjoyable Katas](http://www.codewars.com/users/MrZizoScream/authored)
___

## ALL translations are welcomed

## Enjoy Learning !!
# Zizou

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