vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
problem

One day, Taro, who lives in JOI town, decided to take a walk as a daily routine to improve his health. In JOI town, where Taro lives, he runs in the east-west direction as shown in the figure (H + 1). The road and the north-south direction (W + 1) run through the road in a grid pattern. Taro's house is at the northwestern intersection, and the walk starts from here.

Hereafter, the ath intersection from the north and the bth intersection from the west are represented by (a, b). For example, the intersection where Taro's house is located is (1, 1).


<image>

Figure: JOI town map (for H = 3, W = 4). The top of the figure corresponds to the north and the left corresponds to the west.

Taro thought that it would be more interesting if the walking route was different every day, so he wrote the letters "east" or "south" at the H x W intersections from (1, 1) to (H, W). , I decided to take a walk every day according to the following rules.

* If you are at an intersection with letters, rewrite the letters from "east" to "south" and "south" to "east", and the direction of the originally written letters. Proceed to the next intersection at.
* End the walk when you reach the easternmost or southernmost road.



After thinking about this plan, Taro was wondering what route he would take in his future walks. For Taro, he predicted the route for Taro's Nth walk. Create a program to do.



input

The input consists of multiple datasets. Each dataset is given in the following format.

On the first line, three positive integers are separated by blanks. These are the values ​​of the three numbers H, W, N in the problem statement. H, W, N are 1 ≤ H ≤, respectively. 1000, 1 ≤ W ≤ 1000, 1 ≤ N ≤ 10000000 = 107. From the 2nd line to H + 1st line, W integers are written separated by blanks. Represents the information of the character written at the intersection first. If the jth integer of i + 1st line is 0, the character written at the intersection (i, j) is "south", and if it is 1, the intersection Indicates that the character written in (i, j) is "east".

Of the scoring data, 30% of the points are satisfied with H ≤ 100, W ≤ 100, and N ≤ 1000.

When H, W, N are all 0, it indicates the end of input. The number of data sets does not exceed 10.

output

Output in the following format for each data set.
When the intersection where Taro finishes the walk in the Nth walk is (i, j), output i and j separated by a blank in this order.

Example

Input

3 4 3
1 0 1 1
0 1 0 0
1 0 1 0
0 0 0


Output

1 5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The chef is trying to solve some pattern problems, Chef wants your help to code it. Chef has one number K to form a new pattern. Help the chef to code this pattern problem.

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input, one integer $K$. 

-----Output:-----
For each test case, output as the pattern.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq K \leq 100$

-----Sample Input:-----
3
2
3
4

-----Sample Output:-----
1121
1222
112131
122232
132333
11213141
12223242
13233343
14243444

-----EXPLANATION:-----
No need, else pattern can be decode easily.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Little Elephant and Problem

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The Little Elephant has got a problem — somebody has been touching his sorted by non-decreasing array *a* of length *n* and possibly swapped some elements of the array.

The Little Elephant doesn't want to call the police until he understands if he could have accidentally changed the array himself. He thinks that he could have accidentally changed array *a*, only if array *a* can be sorted in no more than one operation of swapping elements (not necessarily adjacent). That is, the Little Elephant could have accidentally swapped some two elements.

Help the Little Elephant, determine if he could have accidentally changed the array *a*, sorted by non-decreasing, himself.

Input Specification:
The first line contains a single integer *n* (2<=≤<=*n*<=≤<=105) — the size of array *a*. The next line contains *n* positive integers, separated by single spaces and not exceeding 109, — array *a*.

Note that the elements of the array are not necessarily distinct numbers.

Output Specification:
In a single line print "YES" (without the quotes) if the Little Elephant could have accidentally changed the array himself, and "NO" (without the quotes) otherwise.

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

Demo Output:
['YES\n', 'YES\n', 'NO\n']

Note:
In the first sample the array has already been sorted, so to sort it, we need 0 swap operations, that is not more than 1. Thus, the answer is "YES".

In the second sample we can sort the array if we swap elements 1 and 3, so we need 1 swap operation to sort the array. Thus, the answer is "YES".

In the third sample we can't sort the array in more than one swap operation, so the answer is "NO".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider the string `"1 2 36 4 8"`. Lets take pairs of these numbers, concatenate each pair and determine how many of them of divisible by `k`. 

```Pearl 
If k = 3, we get following numbers ['12', '18', '21', '24', '42', '48', '81', '84'], all divisible by 3.   
Note:
-- 21 and 12 are different pairs. 
-- Elements must be from different indices, so '3636` is not a valid. 
```

Given a string of numbers and an integer `k`, return the number of pairs that when concatenated, are divisible by `k`.

```
solve("1 2 36 4 8", 3) = 8, because they are ['12', '18', '21', '24', '42', '48', '81', '84']
solve("1 3 6 3", 3) = 6. They are ['36', '33', '63', '63', '33', '36']
```

More examples in test cases. Good luck!

Please also try [Simple remove duplicates](https://www.codewars.com/kata/5ba38ba180824a86850000f7)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence a consisting of n integers. Find the maximum possible value of $a_{i} \operatorname{mod} a_{j}$ (integer remainder of a_{i} divided by a_{j}), where 1 ≤ i, j ≤ n and a_{i} ≥ a_{j}.


-----Input-----

The first line contains integer n — the length of the sequence (1 ≤ n ≤ 2·10^5). 

The second line contains n space-separated integers a_{i} (1 ≤ a_{i} ≤ 10^6).


-----Output-----

Print the answer to the problem.


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

Output
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We are given an array A of N lowercase letter strings, all of the same length.
Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.
For example, if we have an array A = ["abcdef","uvwxyz"] and deletion indices {0, 2, 3}, then the final array after deletions is ["bef","vyz"].
Suppose we chose a set of deletion indices D such that after deletions, the final array has its elements in lexicographic order (A[0] <= A[1] <= A[2] ... <= A[A.length - 1]).
Return the minimum possible value of D.length.
 







Example 1:
Input: ["ca","bb","ac"]
Output: 1
Explanation: 
After deleting the first column, A = ["a", "b", "c"].
Now A is in lexicographic order (ie. A[0] <= A[1] <= A[2]).
We require at least 1 deletion since initially A was not in lexicographic order, so the answer is 1.


Example 2:
Input: ["xc","yb","za"]
Output: 0
Explanation: 
A is already in lexicographic order, so we don't need to delete anything.
Note that the rows of A are not necessarily in lexicographic order:
ie. it is NOT necessarily true that (A[0][0] <= A[0][1] <= ...)


Example 3:
Input: ["zyx","wvu","tsr"]
Output: 3
Explanation: 
We have to delete every column.

 


Note:

1 <= A.length <= 100
1 <= A[i].length <= 100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bertown is a city with $n$ buildings in a straight line.

The city's security service discovered that some buildings were mined. A map was compiled, which is a string of length $n$, where the $i$-th character is "1" if there is a mine under the building number $i$ and "0" otherwise.

Bertown's best sapper knows how to activate mines so that the buildings above them are not damaged. When a mine under the building numbered $x$ is activated, it explodes and activates two adjacent mines under the buildings numbered $x-1$ and $x+1$ (if there were no mines under the building, then nothing happens). Thus, it is enough to activate any one mine on a continuous segment of mines to activate all the mines of this segment. For manual activation of one mine, the sapper takes $a$ coins. He can repeat this operation as many times as you want.

Also, a sapper can place a mine under a building if it wasn't there. For such an operation, he takes $b$ coins. He can also repeat this operation as many times as you want.

The sapper can carry out operations in any order.

You want to blow up all the mines in the city to make it safe. Find the minimum number of coins that the sapper will have to pay so that after his actions there are no mines left in the city.


-----Input-----

The first line contains one positive integer $t$ ($1 \le t \le 10^5$) — the number of test cases. Then $t$ test cases follow.

Each test case begins with a line containing two integers $a$ and $b$ ($1 \le a, b \le 1000$) — the cost of activating and placing one mine, respectively.

The next line contains a map of mines in the city — a string consisting of zeros and ones.

The sum of the string lengths for all test cases does not exceed $10^5$.


-----Output-----

For each test case, output one integer — the minimum number of coins that the sapper will have to pay.


-----Example-----
Input
2
1 1
01000010
5 1
01101110

Output
2
6



-----Note-----

In the second test case, if we place a mine under the fourth building and then activate it, then all mines on the field are activated. The cost of such operations is six, $b=1$ coin for placing a mine and $a=5$ coins for activating.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The chef is playing a game of long distance. Chef has a number K and he wants to find the longest distance between the index of the first and the last occurrence of K in a given array of N numbers.

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains two lines of input.
- Next line with Two integers in one line $K, N$.
- Next line with $N$ space-separated integers.

-----Output:-----
For each test case, output in a single line answer as the index of first and last occurrence of K in the given array.
Note: Here Indexing is from 1 not  0 based.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq k \leq 10^5$
- $1 \leq N \leq 10^5$

-----Sample Input:-----
2
2 6
2 3 4 2 1 6
4 6
2 3 4 2 1 6

-----Sample Output:-----
3
0

-----EXPLANATION:-----
For 1) Index of First and last occurrence of 2 in the given array is at 1 and 4, i.e. distance is 3. 
For 2) 4 occurs only once in the given array hence print 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The night after the graduation ceremony graduate students of German University in Cairo (GUC) are playing darts. As there's no real dart board available, the photographs of members of the GUC upper management are being used.

So, n rectangular photos are placed on the wall. They can overlap arbitrary and even coincide. The photos are not necessarily placed horizontally or vertically, they could also be rotated before being pinned to the wall.

The score of one dart throw is simply the number of photos the dart went through.

Fatma has made a throw but her score was not recorded. She only remembers that she did make it into at least one photo.

Assuming that the probability distribution of the throw is equal across the whole wall, what would be the expectation of Fatma's score?

Input

The first line of input contains integer n (1 ≤ n ≤ 500) — the number of photos on the wall. Then follow n lines describing the photos, each containing 8 single-space-separated integers (coordinates of 4 vertices): x1, y1, x2, y2, x3, y3, x4, y4. Each photo is a rectangle with a nonzero area. The coordinates are integers, not exceeding 104 by absolute value. The coordinates of the rectangle are given in either clockwise or counterclockwise order.

Output

Print the expected score of the throw. The answer will be accepted if it has absolute or relative error not exceeding 10 - 6.

Examples

Input

1
0 0 0 2 2 2 2 0


Output

1.0000000000


Input

1
-1 0 0 1 1 0 0 -1


Output

1.0000000000


Input

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


Output

1.5000000000


Input

2
-1 0 0 1 1 0 0 -1
0 0 1 1 2 0 1 -1


Output

1.1428571429

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Time Limit: 8 sec / Memory Limit: 64 MB





Example

Input

10 10
.....#....
.....#....
.....#....
######....
..........
####......
....###...
t..#..####
...##.....
....#...##
3
0 3
0 5
4 6


Output

2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Andrew often reads articles in his favorite magazine 2Char. The main feature of these articles is that each of them uses at most two distinct letters. Andrew decided to send an article to the magazine, but as he hasn't written any article, he just decided to take a random one from magazine 26Char. However, before sending it to the magazine 2Char, he needs to adapt the text to the format of the journal. To do so, he removes some words from the chosen article, in such a way that the remaining text can be written using no more than two distinct letters.

Since the payment depends from the number of non-space characters in the article, Andrew wants to keep the words with the maximum total length.


-----Input-----

The first line of the input contains number n (1 ≤ n ≤ 100) — the number of words in the article chosen by Andrew. Following are n lines, each of them contains one word. All the words consist only of small English letters and their total length doesn't exceed 1000. The words are not guaranteed to be distinct, in this case you are allowed to use a word in the article as many times as it appears in the input.


-----Output-----

Print a single integer — the maximum possible total length of words in Andrew's article.


-----Examples-----
Input
4
abb
cacc
aaa
bbb

Output
9
Input
5
a
a
bcbcb
cdecdecdecdecdecde
aaaa

Output
6


-----Note-----

In the first sample the optimal way to choose words is {'abb', 'aaa', 'bbb'}.

In the second sample the word 'cdecdecdecdecdecde' consists of three distinct letters, and thus cannot be used in the article. The optimal answer is {'a', 'a', 'aaaa'}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Solve the mystery.  
Input:
String which consists of words(all the characters of any word are lower case letters) and punctuation marks(consists of {'.' , ',' , '?' , '!'}). Also every input string consists of one '*' in it.
It is guaranteed that strings doesn't start or end with space(' ') and only one answer exists for each case.  

Output:
Lower case letter.  

Constrains:
1 ≤ t ≤ 1000
2 ≤ length of string(n) ≤ 100  

Problem Setter : Vinay Kumar

SAMPLE INPUT
7
k! cats s*ack.
ah, s*tan sees natasha!
aibohphobi*
al lets della call ed ste*la.
amy, must i jujitsu *y ma?
aerata pat a*ea.
lollipop i * lol.

SAMPLE OUTPUT
t
a
a
l
m
r
l

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a program which manipulates a sequence $A = \\{a_0, a_1, ..., a_{n-1}\\}$ by the following operations:

* min($b, e$): report the minimum element in $a_b, a_{b+1}, ..., a_{e-1}$
* max($b, e$): report the maximum element in $a_b, a_{b+1}, ..., a_{e-1}$

Constraints

* $1 \leq n \leq 1,000$
* $-1,000,000,000 \leq a_i \leq 1,000,000,000$
* $1 \leq q \leq 1,000$
* $0 \leq b < e \leq n$

Input

The input is given in the following format.


$n$
$a_0 \; a_1, ..., \; a_{n-1}$
$q$
$com_1 \; b_1 \; e_1$
$com_2 \; b_2 \; e_2$
:
$com_{q} \; b_{q} \; e_{q}$


In the first line, $n$ (the number of elements in $A$) is given. In the second line, $a_i$ (each element in $A$) are given. In the third line, the number of queries $q$ is given and each query is given in the following $q$ lines. $com_i$ denotes a type of query. 0 and 1 represents min($b, e$) and max($b, e$) respectively.

Output

For each query, print the minimum element or the maximum element in a line.

Example

Input

7
8 3 7 1 9 1 4
3
0 0 3
0 1 5
1 0 7


Output

3
1
9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Rook, Bishop and King

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little Petya is learning to play chess. He has already learned how to move a king, a rook and a bishop. Let us remind you the rules of moving chess pieces. A chessboard is 64 square fields organized into an 8<=×<=8 table. A field is represented by a pair of integers (*r*,<=*c*) — the number of the row and the number of the column (in a classical game the columns are traditionally indexed by letters). Each chess piece takes up exactly one field. To make a move is to move a chess piece, the pieces move by the following rules:
 -  A rook moves any number of fields horizontally or vertically. -  A bishop moves any number of fields diagonally. -  A king moves one field in any direction — horizontally, vertically or diagonally. 
Petya is thinking about the following problem: what minimum number of moves is needed for each of these pieces to move from field (*r*1,<=*c*1) to field (*r*2,<=*c*2)? At that, we assume that there are no more pieces besides this one on the board. Help him solve this problem.

Input Specification:
The input contains four integers *r*1,<=*c*1,<=*r*2,<=*c*2 (1<=≤<=*r*1,<=*c*1,<=*r*2,<=*c*2<=≤<=8) — the coordinates of the starting and the final field. The starting field doesn't coincide with the final one.

You can assume that the chessboard rows are numbered from top to bottom 1 through 8, and the columns are numbered from left to right 1 through 8.

Output Specification:
Print three space-separated integers: the minimum number of moves the rook, the bishop and the king (in this order) is needed to move from field (*r*1,<=*c*1) to field (*r*2,<=*c*2). If a piece cannot make such a move, print a 0 instead of the corresponding number.

Demo Input:
['4 3 1 6\n', '5 5 5 6\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snowden as we all know is good at stealing and parsing the resources from the internet. He has been threatened by the intelligence agencies to find our parliamentary members for surveillance in one day time. The data would be safe if we are able to collect all the links in a site before him. So our goal is given a webpage source we have to extract all the links going to the same site.

A link will look like this

Note :

The order of links need to be preserved.i.e. the document needs to be scanned from left-right top-bottom fashion.

Input :

The First line is the website name.

Followed by the html content that ends with the string “exit” in a new line.

1 ≤ Length of each line ≤ 500

1 ≤ total number of lines ≤ 25

Output:

Output all the links that links to the same site.

SAMPLE INPUT
http://www.knowyourcandidate.net
<html>
<head>
<title></title>
</head>
<body>
<a href="http://www.knowyourcandidate.net/web/ministers/list/1">List Of Ministers</a>
<a href="http://www.knowyourcandidate.net/mla-tamilnadu">Tamil Nadu MLA's</a>
<a href="http://www.facebook.com/knowurcandidate">Like us on Facebook</a>
<a href="http://plus.google.com/knowyourcandidate">Plus 1 on Google+</a>
</body>
</html>
exit

SAMPLE OUTPUT
http://www.knowyourcandidate.net/web/ministers/list/1
http://www.knowyourcandidate.net/mla-tamilnadu

Explanation

The first Two links, links to the same site www.knowyoucandidate.net whereas the next two links will go to facebook.com and plus.google.com

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vitaly is a diligent student who never missed a lesson in his five years of studying in the university. He always does his homework on time and passes his exams in time. 

During the last lesson the teacher has provided two strings *s* and *t* to Vitaly. The strings have the same length, they consist of lowercase English letters, string *s* is lexicographically smaller than string *t*. Vitaly wondered if there is such string that is lexicographically larger than string *s* and at the same is lexicographically smaller than string *t*. This string should also consist of lowercase English letters and have the length equal to the lengths of strings *s* and *t*. 

Let's help Vitaly solve this easy problem!

Input Specification:
The first line contains string *s* (1<=≤<=|*s*|<=≤<=100), consisting of lowercase English letters. Here, |*s*| denotes the length of the string.

The second line contains string *t* (|*t*|<==<=|*s*|), consisting of lowercase English letters.

It is guaranteed that the lengths of strings *s* and *t* are the same and string *s* is lexicographically less than string *t*.

Output Specification:
If the string that meets the given requirements doesn't exist, print a single string "No such string" (without the quotes).

If such string exists, print it. If there are multiple valid strings, you may print any of them.

Demo Input:
['a\nc\n', 'aaa\nzzz\n', 'abcdefg\nabcdefh\n']

Demo Output:
['b\n', 'kkk\n', 'No such string\n']

Note:
String *s* = *s*<sub class="lower-index">1</sub>*s*<sub class="lower-index">2</sub>... *s*<sub class="lower-index">*n*</sub> is said to be lexicographically smaller than *t* = *t*<sub class="lower-index">1</sub>*t*<sub class="lower-index">2</sub>... *t*<sub class="lower-index">*n*</sub>, if there exists such *i*, 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>, *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.
# Task
 You are given two strings s and t of the same length, consisting of uppercase English letters. Your task is to find the minimum number of "replacement operations" needed to get some `anagram` of the string t from the string s. A replacement operation is performed by picking exactly one character from the string s and replacing it by some other character.

 About `anagram`: А string x is an anagram of a string y if one can get y by rearranging the letters of x. For example, the strings "MITE" and "TIME" are anagrams, so are "BABA" and "AABB", but "ABBAC" and "CAABA" are not.

# Example

 For s = "AABAA" and t = "BBAAA", the output should be 1;
 
 For s = "OVGHK" and t = "RPGUC", the output should be 4.
 
# Input/Output


 - `[input]` string `s`

    Constraints: `5 ≤ s.length ≤ 35`.


 - `[input]` string `t`

    Constraints: `t.length = s.length`.


 - `[output]` an integer

    The minimum number of replacement operations needed to get an anagram of the string t from the string s.

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