vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The volume of access to a web service varies from time to time in a day. Also, the hours with the highest volume of access varies from service to service. For example, a service popular in the United States may receive more access in the daytime in the United States, while another service popular in Japan may receive more access in the daytime in Japan. When you develop a web service, you have to design the system so it can handle all requests made during the busiest hours.

You are a lead engineer in charge of a web service in the 30th century. It’s the era of Galaxy Wide Web (GWW), thanks to the invention of faster-than-light communication. The service can be accessed from all over the galaxy. Thus many intelligent creatures, not limited to human beings, can use the service. Since the volume of access to your service is increasing these days, you have decided to reinforce the server system. You want to design a new system that handles requests well even during the hours with the highest volume of access. However, this is not a trivial task. Residents in each planet have their specific length of a day, say, a cycle of life. The length of a day is not always 24 hours. Therefore, a cycle of the volume of access are different by planets of users.

You have obtained hourly data of the volume of access for all planets where you provide the service. Assuming the volume of access follows a daily cycle for each planet, you want to know the highest volume of access in one hour. It should be a quite easy task for you, a famous talented engineer in the galaxy.



Input

The input consists of multiple datasets. Each dataset has the following format:

N
d1 t1 q1,0 ... q1,d1-1
...
dN tN qN,0 ... qN,dN-1


N is the number of planets. di (1 ≤ i ≤ N) is the length of a day in the planet i.  ti (0 ≤ ti ≤ di - 1) is the current time of the planet i. qi, j is the volume of access on the planet i during from the j-th hour to the (j+1)-th hour.

You may assume that N ≤ 100, di ≤ 24, qi, j ≤ 1000000 (1 ≤ i ≤ N, 0 ≤ j ≤ di - 1).

The last dataset is followed by a line containing one zero. This line is not a part of any dataset and should not be processed.

Output

For each dataset, output the maximum volume of access in one hour in a line.

Example

Input

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


Output

5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The New Year is coming! That's why many people today are busy preparing New Year presents. Vasily the Programmer is no exception.

Vasily knows that the best present is (no, it's not a contest) money. He's put n empty wallets from left to right in a row and decided how much money to put in what wallet. Vasily decided to put ai coins to the i-th wallet from the left.

Vasily is a very busy man, so the money are sorted into the bags by his robot. Initially, the robot stands by the leftmost wallet in the row. The robot can follow instructions of three types: go to the wallet that is to the left of the current one (if such wallet exists), go to the wallet that is to the right of the current one (if such wallet exists), put a coin to the current wallet. Due to some technical malfunctions the robot cannot follow two "put a coin" instructions in a row.

Vasily doesn't want to wait for long, so he wants to write a program for the robot that contains at most 106 operations (not necessarily minimum in length) the robot can use to put coins into the wallets. Help him.

Input

The first line contains integer n (2 ≤ n ≤ 300) — the number of wallets. The next line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 300).

It is guaranteed that at least one ai is positive.

Output

Print the sequence that consists of k (1 ≤ k ≤ 106) characters, each of them equals: "L", "R" or "P". Each character of the sequence is an instruction to the robot. Character "L" orders to move to the left, character "R" orders to move to the right, character "P" orders the robot to put a coin in the wallet. The robot is not allowed to go beyond the wallet line. In other words, you cannot give instructions "L" if the robot is at wallet 1, or "R" at wallet n.

As a result of the performed operations, the i-th wallet from the left must contain exactly ai coins. If there are multiple answers, you can print any of them.

Examples

Input

2
1 2


Output

PRPLRP

Input

4
0 2 0 2


Output

RPRRPLLPLRRRP

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Cars! Where do they come from? Where do they go? Nobody knows. They appear where roads have been built, as if out of nowhere. Some say that no two cars are alike. Some say that if you look closely, you can see the pale ghosts of miserable humans inside them, trapped forever—particularly in the morning and late afternoon. What scientific eye could frame their fearful symmetry?

Well, yours, hopefully. As part of your government’s Urban Traffic Control department, you are trying to write a paper on local traffic congestion. It is too dangerous to observe cars in the wild, of course, but you have been given some data on the traffic lights along your town’s Main Street, and you would like to do some theoretical calculations about how well-synchronized they are.

Main Street is set out on a line, with traffic lights placed at various points along it. Each traffic light cycles between red and green with a fixed period, being red for $r$ seconds, then green for $g$ seconds, then red for $r$ seconds, and so on. The values of $r$ and $g$ may be different for different traffic lights. At time $0$, all the lights have just turned red.

Assume that an “ideal” car mystically appears at the west end of Main Street at a uniformly random real-valued time in the interval $[0, 2019!]$ (where $k!$ is the product of the first $k$ positive integers), driving eastwards at a slow crawl of $1$ meter/second until it hits a red light. What is the probability that it will make it through all the lights without being forced to stop? If it does hit a red light, which one is it likely to hit first?

Write a program to answer these questions.

-----Input-----
The first line of input contains an integer $n$ ($1 \le n \le 500$), the number of traffic lights. Each of the following $n$ lines contains three integers $x$, $r$, and $g$ describing a traffic light, where $x$ ($1 \le x \le 10^5$) is the position of the light along Main Street in meters, and $r$ and $g$ ($0 \le r, g$ and $1 \le r+g \le 100$) are the durations in seconds of the red and green portions of the light’s period (so the light is red from time $0$ to $r$, from time $r+g$ to $2r+g$, and so on).

The west end of Main Street is at position $0$, and the lights are listed in order of strictly increasing position.

-----Output-----
For each of the $n$ lights, output a line containing the probability that this light will be the first red light an “ideal” car hits. Then output a line containing the probability that an “ideal” car makes it all the way without stopping. Your answers should have an absolute error of at most $10^{-6}$.

-----Examples-----
Sample Input:
4
1 2 3
6 2 3
10 2 3
16 3 4
Sample Output:
0.4
0
0.2
0.171428571429
0.228571428571

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S and another string patt. Find the character in patt that is present at the minimum index in S.
 
Example 1:
Input: S = "zsyle", patt = "bjz"
Output: "z"
Example 2:
Input: S = "anskg", patt = "me"
Output: "$"
 
Your Task:
You don't need to read or print anything. Your task is to complete the function printMinIndexChar() which takes S and patt as input parameter and returns the character in patt that is present at the minimum index in S. If not possible returns "$".
 
Expected Time Complexity: O(max(|str|, |patt|))
Expected Auxilary Space: O(K) where K <= 26
 
Constraints:
1 ≤ |S|, |patt| ≤ 10^{4}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two positive integers num1 and num2, the task is to find the sum of the two numbers on a 12 hour clock rather than a number line.
Example 1:
Input: num1 = 5, num2 = 7
Output: 0
Explaination: 5+7=12, which in 12 hour 
clock format is 0.
Example 2:
Input: num1 = 3, num2 = 5
Output: 8
Explaination: 3+5=8, which is 12 hour 
format is intact.
Your Task:
You do not need to read input or print anythign. Your task is to complete the function clockSum() which takes num1 and num2 as input parameters and returns the 12 hour clock format addition of the numbers.
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ num1, num2 ≤ 50

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Karafs is some kind of vegetable in shape of an 1<=×<=*h* rectangle. Tavaspolis people love Karafs and they use Karafs in almost any kind of food. Tavas, himself, is crazy about Karafs.

Each Karafs has a positive integer height. Tavas has an infinite 1-based sequence of Karafses. The height of the *i*-th Karafs is *s**i*<==<=*A*<=+<=(*i*<=-<=1)<=×<=*B*.

For a given *m*, let's define an *m*-bite operation as decreasing the height of at most *m* distinct not eaten Karafses by 1. Karafs is considered as eaten when its height becomes zero.

Now SaDDas asks you *n* queries. In each query he gives you numbers *l*, *t* and *m* and you should find the largest number *r* such that *l*<=≤<=*r* and sequence *s**l*,<=*s**l*<=+<=1,<=...,<=*s**r* can be eaten by performing *m*-bite no more than *t* times or print -1 if there is no such number *r*.

Input Specification:
The first line of input contains three integers *A*, *B* and *n* (1<=≤<=*A*,<=*B*<=≤<=106, 1<=≤<=*n*<=≤<=105).

Next *n* lines contain information about queries. *i*-th line contains integers *l*,<=*t*,<=*m* (1<=≤<=*l*,<=*t*,<=*m*<=≤<=106) for *i*-th query.

Output Specification:
For each query, print its answer in a single line.

Demo Input:
['2 1 4\n1 5 3\n3 3 10\n7 10 2\n6 4 8\n', '1 5 2\n1 5 10\n2 7 4\n']

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

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Two polar bears Menshykov and Uslada from the St.Petersburg zoo and elephant Horace from the Kiev zoo got six sticks to play with and assess the animals' creativity. Menshykov, Uslada and Horace decided to make either an elephant or a bear from those sticks. They can make an animal from sticks in the following way: 
 -  Four sticks represent the animal's legs, these sticks should have the same length. -  Two remaining sticks represent the animal's head and body. The bear's head stick must be shorter than the body stick. The elephant, however, has a long trunk, so his head stick must be as long as the body stick. Note that there are no limits on the relations between the leg sticks and the head and body sticks. 
Your task is to find out which animal can be made from the given stick set. The zoo keeper wants the sticks back after the game, so they must never be broken, even bears understand it.

Input Specification:
The single line contains six space-separated integers *l**i* (1<=≤<=*l**i*<=≤<=9) — the lengths of the six sticks. It is guaranteed that the input is such that you cannot make both animals from the sticks.

Output Specification:
If you can make a bear from the given set, print string "Bear" (without the quotes). If you can make an elephant, print string "Elephant" (wıthout the quotes). If you can make neither a bear nor an elephant, print string "Alien" (without the quotes).

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

Demo Output:
['Bear', 'Elephant', 'Alien']

Note:
If you're out of creative ideas, see instructions below which show how to make a bear and an elephant in the first two samples. The stick of length 2 is in red, the sticks of length 4 are in green, the sticks of length 5 are in blue.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a permutation P = (p1, p2, ..., pN) of numbers [1, 2, ..., N], we define the function f(P) = max(p1, p2) + max(p2, p3) + ... + max(pN-1, pN).
You are given N and an integer K. Find and report a permutation P of [1, 2, ..., N] such that f(P) = K, if such a permutation exists.
Note f([1]) = 0.

-----Input-----
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- The only line of each test case consists of two space-separated integers N, K respectively.

-----Output-----
For each test case, if a permutation satisfying the condition exists, output a single line containing N space-separated integers which denotes any such permutation. If no such permutation exists, output a single integer -1 instead.
Use fast I/O methods since the size of the output is large.

-----Constraints-----
- 1 ≤ T ≤ 40
- 1 ≤ N ≤ 105
- Sum of N over all test cases in each file ≤ 106
- 0 ≤ K ≤ 2 * 1010

-----Example-----
Input:
3
4 12
2 2
5 14

Output:
-1
1 2
5 4 3 2 1

-----Explanation-----
Example 1. There doesn't exist any permutation of numbers [1, 2, 3, 4] that can have its f value equal to 4. Hence answer is -1.
Example 2. The permutations [1, 2] and [2, 1] both have their f values equal to 2. You can print any of these two permutations. 
Example 3. The permutation [5, 4, 3, 2, 1]
has f value = max(5, 4) + max(4, 3) + max(3, 2) + max(2, 1) = 5 + 4 + 3 + 2 = 14.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S, sort it in the following manner. Sorted string must contain a vowel as first letter and a consonant as next letter and so on OR a consonant as first letter and a vowel as next letter and so on, depending on the string. If there is no vowel left then print the remaining consonant in ascending order and vice versa. 
Note: Order of vowel must be a->e->i->o->u and order of consonant must be b->c->d... and so on.
Example 1: 
Input: abcdei 
Output: abecid 
Explanation: 'a' (Vowel) came first so the
pattern of sorted string is vcvcvcvc... 
Example 2: 
Input: bcadefgh
Output: bacedfgh 
Explanation: 'b' (consonant) came first so
the pattern of sorted string is cvcvcvcv....
 
Your Task: 
You don't need to read input or print anything. Your task is to complete the function SortedString() which takes the string s as input parameters and returns the sorted string. 
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints:
1<=|S|<=1000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of strings, return all groups of strings that are anagrams. The groups must be created in order of their appearance in the original array. Look at the sample case for clarification.
Note: The final output will be in lexicographic order.
Example 1:
Input:
N = 5
words[] = {act,god,cat,dog,tac}
Output:
act cat tac 
god dog
Explanation:
There are 2 groups of
anagrams "god", "dog" make group 1.
"act", "cat", "tac" make group 2.
Example 2:
Input:
N = 3
words[] = {no,on,is}
Output: 
is
no on
Explanation:
There are 2 groups of
anagrams "is" makes group 1.
"no", "on" make group 2.
Your Task:
The task is to complete the function Anagrams() that takes a list of strings as input and returns a list of groups such that each group consists of all the strings that are anagrams.
Expected Time Complexity: O(N*|S|*log|S|), where |S| is the length of the strings.
Expected Auxiliary Space: O(N*|S|), where |S| is the length of the strings.
Constraints:
1<=N<=100
1<=|S|<=10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Calculate the number of ways to color an N * M grid using K colors. Adjacent squares in the grid should have different colors. Squares are considered adjacent if they share an edge.

Input Format 

The first line contains an integer T denoting the number of test-cases.
The next T lines contains integers N, M and K separated by a single space. 

Output Format 

Output T lines, one for each test case containing the number of ways modulo 10^{9}+7. 

Constraints 

1 <= T <= 10^{5} 

1 <= N,M <= 8 

1 <= K <= 10^{9}    

Sample Input

3
3 3 2
3 4 3
1 1 1

Sample Output 

2
1122
1

Explanation 

For the first case, there are two ways to color the grid. The colorings are in a chessboard pattern with either color at the top right square.

Timelimits
Timelimits for this challenge can be seen here

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef loves triangles. But the chef is poor at maths. Given three random lengths Chef wants to find if the three sides form a right-angled triangle or not. Can you help Chef in this endeavour?

-----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, three Integers $A,B and C$

-----Output:-----
For each test case, output in a single line "YES" if it is possible to form a triangle using the given numbers or "NO" if it is not possible to form a triangle.

-----Constraints-----
- $1 \leq T \leq 1000000$
- $0 \leq A,B,C \leq 100$

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

-----Sample Output:-----
YES
NO

-----EXPLANATION:-----
3,4,5 forms a right-angled triangle. 1, 3 and 4 does not form a right-angled triangle.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Joy is a short and lazy guy, he uses elevator to reach his flat. But unfortunately elevator is not working today and he became sad. Suddenly God came and made the stairs magical, such that he can jump on it in a magical way. Initially he can take 1 or 2  steps. If he jumps x steps at a time then in the next step he can climb either x or x+1 steps depending on his choice and he must reach exactly on n'th step. Help him find the minimum number of jumps to be made.

INPUT

First line will contain t, total number of test case
Next t lines contains n (total number of steps).

0<t ≤ 100

0<n ≤ 10^5

OUTPUT

Minimum steps to reach the stairs.

SAMPLE INPUT
2
2
3

SAMPLE OUTPUT
1
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In mathematics, a matrix (plural matrices) is a rectangular array of numbers. Matrices have many applications in programming, from performing transformations in 2D space to machine learning. 

One of the most useful operations to perform on matrices is matrix multiplication, which takes a pair of matrices and produces another matrix – known as the dot product. Multiplying matrices is very different to multiplying real numbers, and follows its own set of rules. 

Unlike multiplying real numbers, multiplying matrices is non-commutative: in other words, multiplying matrix ```a``` by matrix ```b``` will not give the same result as multiplying matrix ```b``` by matrix ```a```.

Additionally, not all pairs of matrix can be multiplied. For two matrices to be multipliable, the number of columns in matrix ```a``` must match the number of rows in matrix ```b```.

There are many introductions to matrix multiplication online, including at Khan Academy, and in the classic MIT lecture series by Herbert Gross. 

To complete this kata, write a function that takes two matrices - ```a``` and ```b``` - and returns the dot product of those matrices. If the matrices cannot be multiplied, return ```-1``` for JS/Python, or `null` for Java.

Each matrix will be represented by a two-dimensional list (a list of lists). Each inner list will contain one or more numbers, representing a row in the matrix.

For example, the following matrix:

```|1 2|``````|3 4|```

Would be represented as:

```[[1, 2], [3, 4]]```

It can be assumed that all lists will be valid matrices, composed of lists with equal numbers of elements, and which contain only numbers. The numbers may include integers and/or decimal points.

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 (odd) 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:-----
4
1
3
5
7

-----Sample Output:-----
*
*
**
*
*
**
* *
**
*
*
**
* *
*  *
* *
**
*

-----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.
The map of the capital of Berland can be viewed on the infinite coordinate plane. Each point with integer coordinates contains a building, and there are streets connecting every building to four neighbouring buildings. All streets are parallel to the coordinate axes.

The main school of the capital is located in $(s_x, s_y)$. There are $n$ students attending this school, the $i$-th of them lives in the house located in $(x_i, y_i)$. It is possible that some students live in the same house, but no student lives in $(s_x, s_y)$.

After classes end, each student walks from the school to his house along one of the shortest paths. So the distance the $i$-th student goes from the school to his house is $|s_x - x_i| + |s_y - y_i|$.

The Provision Department of Berland has decided to open a shawarma tent somewhere in the capital (at some point with integer coordinates). It is considered that the $i$-th student will buy a shawarma if at least one of the shortest paths from the school to the $i$-th student's house goes through the point where the shawarma tent is located. It is forbidden to place the shawarma tent at the point where the school is located, but the coordinates of the shawarma tent may coincide with the coordinates of the house of some student (or even multiple students).

You want to find the maximum possible number of students buying shawarma and the optimal location for the tent itself.


-----Input-----

The first line contains three integers $n$, $s_x$, $s_y$ ($1 \le n \le 200\,000$, $0 \le s_x, s_y \le 10^{9}$) — the number of students and the coordinates of the school, respectively.

Then $n$ lines follow. The $i$-th of them contains two integers $x_i$, $y_i$ ($0 \le x_i, y_i \le 10^{9}$) — the location of the house where the $i$-th student lives. Some locations of houses may coincide, but no student lives in the same location where the school is situated.


-----Output-----

The output should consist of two lines. The first of them should contain one integer $c$ — the maximum number of students that will buy shawarmas at the tent. 

The second line should contain two integers $p_x$ and $p_y$ — the coordinates where the tent should be located. If there are multiple answers, print any of them. Note that each of $p_x$ and $p_y$ should be not less than $0$ and not greater than $10^{9}$.


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

Output
3
4 2

Input
3 100 100
0 0
0 0
100 200

Output
2
99 100

Input
7 10 12
5 6
20 23
15 4
16 5
4 54
12 1
4 15

Output
4
10 11



-----Note-----

In the first example, If we build the shawarma tent in $(4, 2)$, then the students living in $(4, 2)$, $(4, 1)$ and $(5, 1)$ will visit it.

In the second example, it is possible to build the shawarma tent in $(1, 1)$, then both students living in $(0, 0)$ will visit it.

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