vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Characteristics of Rectangles

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Gerald found a table consisting of *n* rows and *m* columns. As a prominent expert on rectangular tables, he immediately counted the table's properties, that is, the minimum of the numbers in the corners of the table (minimum of four numbers). However, he did not like the final value — it seemed to be too small. And to make this value larger, he decided to crop the table a little: delete some columns on the left and some on the right, as well as some rows from the top and some from the bottom. Find what the maximum property of the table can be after such cropping. Note that the table should have at least two rows and at least two columns left in the end. The number of cropped rows or columns from each of the four sides can be zero.

Input Specification:
The first line contains two space-separated integers *n* and *m* (2<=≤<=*n*,<=*m*<=≤<=1000). The following *n* lines describe the table. The *i*-th of these lines lists the space-separated integers *a**i*,<=1,<=*a**i*,<=2,<=...,<=*a**i*,<=*m* (0<=≤<=*a**i*,<=*j*<=≤<=109) — the *m* numbers standing in the *i*-th row of the table.

Output Specification:
Print the answer to the problem.

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

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

Note:
In the first test case Gerald cannot crop the table — table contains only two rows and only two columns.

In the second test case if we'll crop the table, the table will contain zero in some corner cell. Also initially it contains two zeros in the corner cells, so the answer is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This time the Berland Team Olympiad in Informatics is held in a remote city that can only be reached by one small bus. Bus has n passenger seats, seat i can be occupied only by a participant from the city a_{i}.

Today the bus has completed m trips, each time bringing n participants. The participants were then aligned in one line in the order they arrived, with people from the same bus standing in the order of their seats (i. e. if we write down the cities where the participants came from, we get the sequence a_1, a_2, ..., a_{n} repeated m times).

After that some teams were formed, each consisting of k participants form the same city standing next to each other in the line. Once formed, teams left the line. The teams were formed until there were no k neighboring participants from the same city.

Help the organizers determine how many participants have left in the line after that process ended. We can prove that answer doesn't depend on the order in which teams were selected.


-----Input-----

The first line contains three integers n, k and m (1 ≤ n ≤ 10^5, 2 ≤ k ≤ 10^9, 1 ≤ m ≤ 10^9).

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5), where a_{i} is the number of city, person from which must take seat i in the bus. 


-----Output-----

Output the number of remaining participants in the line.


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

Output
12

Input
1 9 10
1

Output
1

Input
3 2 10
1 2 1

Output
0



-----Note-----

In the second example, the line consists of ten participants from the same city. Nine of them will form a team. At the end, only one participant will stay in the line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are $n$ water tanks in a row, $i$-th of them contains $a_i$ liters of water. The tanks are numbered from $1$ to $n$ from left to right.

You can perform the following operation: choose some subsegment $[l, r]$ ($1\le l \le r \le n$), and redistribute water in tanks $l, l+1, \dots, r$ evenly. In other words, replace each of $a_l, a_{l+1}, \dots, a_r$ by $\frac{a_l + a_{l+1} + \dots + a_r}{r-l+1}$. For example, if for volumes $[1, 3, 6, 7]$ you choose $l = 2, r = 3$, new volumes of water will be $[1, 4.5, 4.5, 7]$. You can perform this operation any number of times.

What is the lexicographically smallest sequence of volumes of water that you can achieve?

As a reminder:

A sequence $a$ is lexicographically smaller than a sequence $b$ of the same length if and only if the following holds: in the first (leftmost) position where $a$ and $b$ differ, the sequence $a$ has a smaller element than the corresponding element in $b$.


-----Input-----

The first line contains an integer $n$ ($1 \le n \le 10^6$) — the number of water tanks.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — initial volumes of water in the water tanks, in liters.

Because of large input, reading input as doubles is not recommended.


-----Output-----

Print the lexicographically smallest sequence you can get. In the $i$-th line print the final volume of water in the $i$-th tank.

Your answer is considered correct if the absolute or relative error of each $a_i$ does not exceed $10^{-9}$.

Formally, let your answer be $a_1, a_2, \dots, a_n$, and the jury's answer be $b_1, b_2, \dots, b_n$. Your answer is accepted if and only if $\frac{|a_i - b_i|}{\max{(1, |b_i|)}} \le 10^{-9}$ for each $i$.


-----Examples-----
Input
4
7 5 5 7

Output
5.666666667
5.666666667
5.666666667
7.000000000

Input
5
7 8 8 10 12

Output
7.000000000
8.000000000
8.000000000
10.000000000
12.000000000

Input
10
3 9 5 5 1 7 5 3 8 7

Output
3.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
7.500000000
7.500000000



-----Note-----

In the first sample, you can get the sequence by applying the operation for subsegment $[1, 3]$.

In the second sample, you can't get any lexicographically smaller sequence.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array arr containing N words consisting of lowercase characters. Your task is to find the most frequent word in the array. If multiple words have same frequency, then print the word whose first occurence occurs last in the array as compared to the other strings with same frequency.
Example 1:
Input:
N = 3
arr[] = {geeks,for,geeks}
Output: geeks
Explanation: "geeks" comes 2 times.
Example 2:
Input:
N = 2
arr[] = {hello,world}
Output: world
Explanation: "hello" and "world" both
have 1 frequency. We print world as
its first occurence comes last in the
input array.
Your Task:
Complete mostFrequentWord function which takes array of strings and its length as arguments and returns the most frequent word. The printing is done by the driver code.
Expected Time Complexity: O(N * WORD_LEN).
Expected Auxiliary Space: O(N * WORD_LEN).
Constraints:
1 <= N <= 50000
1 <= |each string| <= 50
Sum of length of every string does not exceed 5*10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin Chinese and Vietnamese as well. 

It is well-known that ∑sqrt(a_{i}), a_{i} ∈ N is a root of some integer-coefficient polynomial. For example: sqrt(2) is a root of polynomial: x^{2} − 2. Now, your task is to find not only such polynomial but also the minimal one. When comparing two polynomials, firstly, we consider their degree and then the coefficient of the highest term, and then the second highest term and so on. (Note that we consider only polynomial with the coefficient of highest term is positive)

------ Input ------ 

First line contains an integer T denotes the number of test cases. Each test case is described by an integer n and followed by n space-separated integers a_{i}.

------ Output: ------ 

Each test case print an integer k denotes the degree of polynomial in a single line. Then next line print k + 1  space-separated integers modulo 10^{9} + 7, coefficients from lowest to highest term.

------ Constraints ------ 

1 ≤ T ≤ 5, 1 ≤ n ≤ 15
a_{i} are n distinct primes, 1 ≤ a_{i} ≤ 10^{9}

------ Subtasks ------ 

$Subtask #1: (10 points):  n ≤ 3$
$Subtask #2: (20 points):  n ≤ 5$
$Subtask #3: (30 points):  n ≤ 10$
$Subtask #4: (40 points):  n ≤ 15$

------ Example ------ 

Input:

2
1
2
2
2 3

Output:

2
1000000005 0 1
4
1 0 999999997 0 1

------ Explanation ------ 

The first polynomial is x^{2} − 2, and the second one is x^{4} − 10x^{2} + 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jiva is a self driven car and is out on its very first drive. It aims to earn some revenue by serving as taxi driver.
It starts its journey from a point and travels in a line for 100 Km. It picks and drops passenger on the way,but can accommodate a maximum of M passengers at once. 

Jiva wants be very economical & intends to equally split the fare among the number of passengers as the following :
- The normal rate being - 10 INR/Km for every passenger
- If there are 2 passengers in the car at any part of journey, it gives a 5% discount to both the passengers for that part of the journey.
- If there are 3 or more passengers in the car at any part of journey, it gives a 7% discount to all of them for that part of the journey.
Also note that if the cab was full at any point in the journey,Jiva can not take any more passengers at that time and reports "Cab was full" to its engineers in the end.
Given, a total of N passengers that board Jiva at different points. Find the total revenue earned after the journey completes. 
(See N.B. Section)  

Input:
The first line contains an integer T. T test cases follow.
Second line of each test case contains 2 space-separated integers N and M.
Next N lines contain 2 space-separated integers ( Si and Ei ), the pick up and drop point of the i'th passenger w.r.t the starting point.  

Output: 
Print the revenue earned (Rounded to the nearest integer) followed by "Cab was full" (without the quotes) ,if applicable, in a new line for each test case.  

N.B. If at a particular point of time, Jiva can take some people to fulfill the capacity then it would take the people in preference of the order in which they are mentioned in the problem statement.
Suppose, The input is:
2 1
0 20
0 100
At time T = 0, there are 2 people, but Jiva can take only one of them. It will give higher priority to the person mentioned first i.e. The person with time 0-20.  

Constraints: 
1 ≤ T ≤ 10
0 ≤ N, M ≤ 1000
0 ≤ Si ≤ Ei  ≤ 100  

Note: Candidates need to attempt only one of the given problems

SAMPLE INPUT
2
4 3 
0 100
0 20
30 50
40 80
6 4
10 55
10 20
40 60
55 60
60 70
75 95

SAMPLE OUTPUT
1719 Cab was full
1070

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A repetition-free number is one in which each digit $\{1,2,3,…,9\}$ appears at most once and the digit $0$ does not appear. A repetition-free number can have at most nine digits, but may also have fewer than nine digits. Some examples of repetition-free numbers are $9, 32, 489, 98761$ and $983245$.
You will be given an integer $N$ with at most nine digits. Your task is to print out the smallest repetition-free number bigger than $N$. For example, for $99$ the answer is $123$, for $881$ the answer is $891$, and for $133$ the answer is $134$.

-----Input:-----
A single line with a single integer with at most $9$ digits.

-----Output:-----
A single line containing the smallest repetition-free number bigger than the given number. If there is no repetition-free number bigger than the given number, print $0$.

-----Constraints:-----
- $N$ consists of atmost $9$ digits

-----Sample input-----
99

-----Sample output-----
123

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

Write a function that accepts `msg` string and returns local tops of string from the highest to the lowest.  
The string's tops are from displaying the string in the below way:

```

                                         7891012
                             TUWvXY      6     3
                   ABCDE     S    Z      5
           lmno    z   F     R    1      4
     abc   k  p    v   G     Q    2      3
.34..9 d...j  q....x   H.....P    3......2
125678 efghi  rstuwy   IJKLMNO    45678901

```
The next top is always 1 character higher than the previous one. 
For the above example, the solution for the `123456789abcdefghijklmnopqrstuwyxvzABCDEFGHIJKLMNOPQRSTUWvXYZ123456789012345678910123` input string is `7891012TUWvXYABCDElmnoabc34`. 

- When the `msg` string is empty, return an empty string.
- The input strings may be very long. Make sure your solution has good performance.
- The (.)dots on the sample dispaly of string are only there to help you to understand the pattern  

Check the test cases for more samples.

# Series

- [String tops](https://www.codewars.com/kata/59b7571bbf10a48c75000070)
- [Square string tops](https://www.codewars.com/kata/5aa3e2b0373c2e4b420009af)

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The princess is going to escape the dragon's cave, and she needs to plan it carefully.

The princess runs at *v**p* miles per hour, and the dragon flies at *v**d* miles per hour. The dragon will discover the escape after *t* hours and will chase the princess immediately. Looks like there's no chance to success, but the princess noticed that the dragon is very greedy and not too smart. To delay him, the princess decides to borrow a couple of bijous from his treasury. Once the dragon overtakes the princess, she will drop one bijou to distract him. In this case he will stop, pick up the item, return to the cave and spend *f* hours to straighten the things out in the treasury. Only after this will he resume the chase again from the very beginning.

The princess is going to run on the straight. The distance between the cave and the king's castle she's aiming for is *c* miles. How many bijous will she need to take from the treasury to be able to reach the castle? If the dragon overtakes the princess at exactly the same moment she has reached the castle, we assume that she reached the castle before the dragon reached her, and doesn't need an extra bijou to hold him off.

Input Specification:
The input data contains integers *v**p*,<=*v**d*,<=*t*,<=*f* and *c*, one per line (1<=≤<=*v**p*,<=*v**d*<=≤<=100, 1<=≤<=*t*,<=*f*<=≤<=10, 1<=≤<=*c*<=≤<=1000).

Output Specification:
Output the minimal number of bijous required for the escape to succeed.

Demo Input:
['1\n2\n1\n1\n10\n', '1\n2\n1\n1\n8\n']

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

Note:
In the first case one hour after the escape the dragon will discover it, and the princess will be 1 mile away from the cave. In two hours the dragon will overtake the princess 2 miles away from the cave, and she will need to drop the first bijou. Return to the cave and fixing the treasury will take the dragon two more hours; meanwhile the princess will be 4 miles away from the cave. Next time the dragon will overtake the princess 8 miles away from the cave, and she will need the second bijou, but after this she will reach the castle without any further trouble.

The second case is similar to the first one, but the second time the dragon overtakes the princess when she has reached the castle, and she won't need the second bijou.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sengoku still remembers the mysterious "colourful meteoroids" she discovered with Lala-chan when they were little. In particular, one of the nights impressed her deeply, giving her the illusion that all her fancies would be realized.

On that night, Sengoku constructed a permutation p1, p2, ..., pn of integers from 1 to n inclusive, with each integer representing a colour, wishing for the colours to see in the coming meteor outburst. Two incredible outbursts then arrived, each with n meteorids, colours of which being integer sequences a1, a2, ..., an and b1, b2, ..., bn respectively. Meteoroids' colours were also between 1 and n inclusive, and the two sequences were not identical, that is, at least one i (1 ≤ i ≤ n) exists, such that ai ≠ bi holds.

Well, she almost had it all — each of the sequences a and b matched exactly n - 1 elements in Sengoku's permutation. In other words, there is exactly one i (1 ≤ i ≤ n) such that ai ≠ pi, and exactly one j (1 ≤ j ≤ n) such that bj ≠ pj.

For now, Sengoku is able to recover the actual colour sequences a and b through astronomical records, but her wishes have been long forgotten. You are to reconstruct any possible permutation Sengoku could have had on that night.

Input

The first line of input contains a positive integer n (2 ≤ n ≤ 1 000) — the length of Sengoku's permutation, being the length of both meteor outbursts at the same time.

The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ n) — the sequence of colours in the first meteor outburst.

The third line contains n space-separated integers b1, b2, ..., bn (1 ≤ bi ≤ n) — the sequence of colours in the second meteor outburst. At least one i (1 ≤ i ≤ n) exists, such that ai ≠ bi holds.

Output

Output n space-separated integers p1, p2, ..., pn, denoting a possible permutation Sengoku could have had. If there are more than one possible answer, output any one of them.

Input guarantees that such permutation exists.

Examples

Input

5
1 2 3 4 3
1 2 5 4 5


Output

1 2 5 4 3


Input

5
4 4 2 3 1
5 4 5 3 1


Output

5 4 2 3 1


Input

4
1 1 3 4
1 4 3 4


Output

1 2 3 4

Note

In the first sample, both 1, 2, 5, 4, 3 and 1, 2, 3, 4, 5 are acceptable outputs.

In the second sample, 5, 4, 2, 3, 1 is the only permutation to satisfy the constraints.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Andrewid the Android is a galaxy-famous detective. He is now investigating the case of vandalism at the exhibition of contemporary art.

The main exhibit is a construction of n matryoshka dolls that can be nested one into another. The matryoshka dolls are numbered from 1 to n. A matryoshka with a smaller number can be nested in a matryoshka with a higher number, two matryoshkas can not be directly nested in the same doll, but there may be chain nestings, for example, 1 → 2 → 4 → 5. 

In one second, you can perform one of the two following operations:  Having a matryoshka a that isn't nested in any other matryoshka and a matryoshka b, such that b doesn't contain any other matryoshka and is not nested in any other matryoshka, you may put a in b;  Having a matryoshka a directly contained in matryoshka b, such that b is not nested in any other matryoshka, you may get a out of b. 

According to the modern aesthetic norms the matryoshka dolls on display were assembled in a specific configuration, i.e. as several separate chains of nested matryoshkas, but the criminal, following the mysterious plan, took out all the dolls and assembled them into a single large chain (1 → 2 → ... → n). In order to continue the investigation Andrewid needs to know in what minimum time it is possible to perform this action.


-----Input-----

The first line contains integers n (1 ≤ n ≤ 10^5) and k (1 ≤ k ≤ 10^5) — the number of matryoshkas and matryoshka chains in the initial configuration.

The next k lines contain the descriptions of the chains: the i-th line first contains number m_{i} (1 ≤ m_{i} ≤ n), and then m_{i} numbers a_{i}1, a_{i}2, ..., a_{im}_{i} — the numbers of matryoshkas in the chain (matryoshka a_{i}1 is nested into matryoshka a_{i}2, that is nested into matryoshka a_{i}3, and so on till the matryoshka a_{im}_{i} that isn't nested into any other matryoshka).

It is guaranteed that m_1 + m_2 + ... + m_{k} = n, the numbers of matryoshkas in all the chains are distinct, in each chain the numbers of matryoshkas follow in the ascending order.


-----Output-----

In the single line print the minimum number of seconds needed to assemble one large chain from the initial configuration.


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

Output
1

Input
7 3
3 1 3 7
2 2 5
2 4 6

Output
10



-----Note-----

In the first sample test there are two chains: 1 → 2 and 3. In one second you can nest the first chain into the second one and get 1 → 2 → 3.

In the second sample test you need to disassemble all the three chains into individual matryoshkas in 2 + 1 + 1 = 4 seconds and then assemble one big chain in 6 seconds.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
"N"  White Walkers are positioned  in a circle from "1" to "N". First  (No. 1) White Walker has a dragonglass . He kills the next White Walker (i.e. No. 2) and passes the dragonglass to the next (i.e. No. 3) who kills the 4th and passes the weapon to 5th White Walker. This way alternate killing of White Walkers goes on until only 1 survives. At what position is the survivor? 

Assumption: Always the first White Walker starts to kill with the dragonglass.

Input
'T' No. of test cases.
'N' Total number of White Walkers in  a circle .

Output
The position of the White Walker who survives.

Constraints:
 1 ≤ N ≤ 10^5
 1 ≤ T ≤ 100

SAMPLE INPUT
3
100
10
4

SAMPLE OUTPUT
73
5
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let $f(x)$ be the sum of digits of a decimal number $x$.

Find the smallest non-negative integer $x$ such that $f(x) + f(x + 1) + \dots + f(x + k) = n$.


-----Input-----

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

Each test case consists of one line containing two integers $n$ and $k$ ($1 \le n \le 150$, $0 \le k \le 9$). 


-----Output-----

For each test case, print one integer without leading zeroes. If there is no such $x$ that $f(x) + f(x + 1) + \dots + f(x + k) = n$, print $-1$; otherwise, print the minimum $x$ meeting that constraint.


-----Example-----
Input
7
1 0
1 1
42 7
13 7
99 1
99 0
99 2

Output
1
0
4
-1
599998
99999999999
7997

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