vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are looking for a particular family photo with you and your favorite relatives Alice and Bob. Each family photo contains a line-up of $n$ people. On the photo you’re looking for, you remember that Alice, who is taller than you, was somewhere on your left from the perspective of the photographer. Also, Bob who is taller than both you and Alice, was standing somewhere on your right.

Since you have a large number of family photos, you want to use your computer to assist in finding the photo. Many of the photos are quite blurry, so facial recognition has proven ineffective. Luckily, the Batch Apex Photo Classifier, which detects each person in a photo and outputs the sequence of their (distinct) heights in pixels, has produced excellent results. Given this sequence of heights for $k$ photos, determine which of these photos could potentially be the photo you’re looking for.

-----Input-----
 - The first line contains $1\leq k\leq 1000$, the number of photos you have to process.
 - Then follow two lines for each photo.
 - The first line contains a single integer $3 \leq n \leq 3\cdot 10^5$, the number of people on this photo.
 - The second line contains $n$ distinct integers $1\leq h_1, \dots , h_ n \leq 10^9$, the heights of the people in the photo, from left to right.

It is guaranteed that the total number of people in all photos is at most $3\cdot 10^5$.

-----Output-----
 - On the first line, output the number of photos $k$ that need further investigation.
 - Then print $k$ lines each containing a single integer $1\leq a_ i \leq n$, the sorted indices of the photos you need to look at.

-----Examples-----
Sample Input:
1
3
2 1 3
Sample Output:
1
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Shaun was given $N$ pairs of parenthesis ( )  by his teacher who gave him a difficult task.The task consists of two steps. First,Shaun should colour all $N$ pairs of parenthesis each with different color but opening and closing bracket of a particular pair should be of same colour. Then,Shaun should report to his teacher the number of ways he can arrange all $2*N$ brackets such that sequence form is valid. Teacher defined valid sequence by these rules:
- Any left parenthesis '(' must have a corresponding right parenthesis ')'.
- Any right parenthesis ')' must have a corresponding left parenthesis '('.
- Left parenthesis '(' must go before the corresponding right parenthesis ')'. 
Note: Shaun could match opening and closing brackets of different colours. 
Since number of ways can be large, Shaun would report the answer as modulo 1000000007 ($10^9 + 7$).

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, one integer $N$. 

-----Output:-----
For each testcase, output in a single line answer given by Shaun to his teacher modulo 1000000007.

-----Constraints-----
- $1 \leq T \leq 100000$
- $1 \leq N \leq 100000$

-----Sample Input:-----
3
1
2
3

-----Sample Output:-----
1
6
90

-----EXPLANATION:-----
Here numbers from $1$ to $N$ have been used to denote parenthesis.A unique number corresponds to a unique pair of parenthesis.
-In the first test case , you can use only one color to color the parenthesis  you could arrange it only in one way i.e, 1 1
-In the second test case  you can use two colors and the possible ways of arranging it are
1 1 2 2
1 2 2 1
1 2 1 2
2 2 1 1
2 1 1 2
2 1 2 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
On his Birthday, Utkarsh was given a gift he was most fond of. Utkarsh was given a box which contained lot of Binary Search Trees. When he started to examine the BST's, to his amazement he found that the box contained all possible BST's that can be made using the first N natural numbers.  

But he did not like very tall trees.  Therefore he threw all the BST's that had height greater than H out of the box.
Now the next exciting thing he wanted to do was to count the sum of the integers that are present on the root of each of the remaining tree in the box.

Output the answer Modulo 1000000007

Costraints
0 < N,H ≤ 500  

INPUT
One line containing N and H.
OUTPUT
The answer to the problem.

SAMPLE INPUT
3 3

SAMPLE OUTPUT
10

Explanation

There are  2 trees with 1 as root, 1 tree with 2 as root, 2 trees with 3 as root.
Therefore 2 * 1 + 1 * 2 + 2 * 3 = 10

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Suppose that you are in a campus and have to go for classes day by day. As you may see, when you hurry to a classroom, you surprisingly find that many seats there are already occupied. Today you and your friends went for class, and found out that some of the seats were occupied.

The classroom contains $n$ rows of seats and there are $m$ seats in each row. Then the classroom can be represented as an $n \times m$ matrix. The character '.' represents an empty seat, while '*' means that the seat is occupied. You need to find $k$ consecutive empty seats in the same row or column and arrange those seats for you and your friends. Your task is to find the number of ways to arrange the seats. Two ways are considered different if sets of places that students occupy differs.

Input Specification:
The first line contains three positive integers $n,m,k$ ($1 \leq n, m, k \leq 2\,000$), where $n,m$ represent the sizes of the classroom and $k$ is the number of consecutive seats you need to find.

Each of the next $n$ lines contains $m$ characters '.' or '*'. They form a matrix representing the classroom, '.' denotes an empty seat, and '*' denotes an occupied seat.

Output Specification:
A single number, denoting the number of ways to find $k$ empty seats in the same row or column.

Demo Input:
['2 3 2\n**.\n...\n', '1 2 2\n..\n', '3 3 4\n.*.\n*.*\n.*.\n']

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

Note:
In the first sample, there are three ways to arrange those seats. You can take the following seats for your arrangement. 
 -  $(1,3)$, $(2,3)$ -  $(2,2)$, $(2,3)$ -  $(2,1)$, $(2,2)$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Punctual City is well known for the punctuality of its citizens and its public transportation system. It is particularly famous for its train system. It is always on time, and never too late (or even too early). Statistics about train boarding is regularly collected to keep things running smoothly.

A train has cars numbered $1$ to $N$ (from front to back), each of length $L$ meters. Each car has exactly one door for boarding located at the center ($L/2$ meters from each end of the car). There are no gaps between cars.

When the train stops at the boarding platform, each passenger waiting for the train walks to the door of the car which is closest to them, taking the higher numbered car in the case of a tie.

Given the location of the passengers relative to the train, help the city by reporting the longest distance that any passenger has to walk and the maximum number of passengers boarding any single car.

-----Input-----
The first line of input contains three integers $N$ ($1 \leq N \leq 100$), which is the number of cars of the train, $L$ ($2 \leq L \leq 100$), which is the length of each car, and $P$ ($1 \leq P \leq 1000$), which is the number of passengers waiting for the train. It is guaranteed that $L$ is an even number.

The next $P$ lines describe the location of the passengers relative to the train. Each line contains a single integer $x$ ($0 \leq x \leq 10000$), which is the distance the passenger is behind the front-end of the train.

-----Output-----
Display the longest distance that any passenger has to walk on one line. On the next line, display the maximum number of passengers boarding any single car.

-----Examples-----
Sample Input:
68 90 6
3809
288
2306
2215
4211
379
Sample Output:
27
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The city of Xentopia has a well-connected railway network. The city has $N$ junctions numbered from $1$ to $N$. There are $M$ pairs of railway tracks that exist between the junctions. Trains can travel in both directions on each track. Each railway track is labelled either red, blue, or white in colour.

Tima, a tourist in the city, wants to travel from junction $S$ to junction $T$ in the minimum possible time. She has a map of the railway network that she can use to achieve this goal.

Tima, being rather eccentric, has an interesting constraint for her travel: She wants to travel via exactly $k_1$ red tracks, exactly $k_2$ blue tracks, and any number of white tracks, in any order. She is fine with using a railway track more than once.

Can you tell the minimum time Tima will take to go from $S$ to $T$, ensuring that her constraint is not violated?

-----Input-----
The first line contains four space-separated integers: $N$, ($1 \leq N \leq 450$); $M$, ($1 \leq M \leq 1100$); $k_1$; and $k_2$, ($0 \leq k_1, k_2 \leq 800$, $k_1 \cdot k_2 \leq 800$). Following are $M$ lines. Each line contains four space-separated integers: $U~ V~ X~ C$, denoting that a track exists between junction $U$ and junction $V$, ($1 \leq U, V \leq N$, $U \neq V$); the train covers this track in $X$ seconds, ($0 \leq X \leq 10^9$); and the track is labelled colour $C$, ($0 \leq C \leq 2$). A white track is denoted by $C=0$, a red track is denoted by $C=1$, and a blue track is denoted by $C=2$.

The last line contains two space-separated integers $S$, ($1 \leq S \leq N$), and $T$, ($1 \leq T \leq N$), the source and destination of Tima’s journey, respectively. Note: $S$ may be equal to $T$.

-----Output-----
Print a single integer denoting the total time Tima would take. If it is not possible for Tima to reach her destination using exactly $k_1$ red tracks, $k_2$ blue tracks, and any number of white tracks, output -1.

-----Examples-----
Sample Input:
4 4 1 1
1 2 1 2
1 3 1 0
2 4 1 1
3 4 1 0
1 4
Sample Output:
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jack has become a soldier now. Unfortunately, he has trouble with the drill. Instead of marching beginning with the left foot and then changing legs with each step, as ordered, he keeps repeating a sequence of steps, in which he sometimes makes the wrong steps or — horror of horrors! — stops for a while. For example, if Jack uses the sequence 'right, left, break', when the sergeant yells: 'Left! Right! Left! Right! Left! Right!', Jack first makes a step with the right foot, then one with the left foot, then he is confused and stops for a moment, then again - this time according to the order - starts with the right foot, then uses the left foot, then - to the sergeant's irritation - he stops to catch his breath, to incorrectly start with the right foot again... Marching this way, Jack will make the step that he is supposed to in the given moment in only one third of cases.

When the officers convinced him he should do something about it, Jack decided to modify the basic sequence of steps that he repeats. However, in order not to get too tired, he has decided that the only thing he'll do is adding any number of breaks in any positions of the original sequence (a break corresponds to stopping for the duration of one step). Of course, Jack can't make a step on the same foot twice in a row, if there is no pause between these steps. It is, however, not impossible that the sequence of steps he used so far is incorrect (it would explain a lot, actually).

Help Private Jack! Given the sequence of steps he keeps repeating, calculate the maximal percentage of time that he can spend marching correctly after adding some breaks to his scheme.

Input

The first line of input contains a sequence consisting only of characters 'L', 'R' and 'X', where 'L' corresponds to a step with the left foot, 'R' — with the right foot, and 'X' — to a break. The length of the sequence will not exceed 106.

Output

Output the maximum percentage of time that Jack can spend marching correctly, rounded down to exactly six digits after the decimal point.

Examples

Input

X


Output

0.000000


Input

LXRR


Output

50.000000

Note

In the second example, if we add two breaks to receive LXXRXR, Jack will march: LXXRXRLXXRXRL... instead of LRLRLRLRLRLRL... and will make the correct step in half the cases. If we didn't add any breaks, the sequence would be incorrect — Jack can't step on his right foot twice in a row.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string, and you have to validate whether it's a valid Roman numeral. If it is valid, print True. Otherwise, print False. Try to create a regular expression for a valid Roman numeral.

Input Format

A single line of input containing a string of Roman characters.

Output Format

Output a single line containing True or False according to the instructions above.

Constraints

The number will be between $\mbox{I}$ and $\textbf{3999}$ (both included).

Sample Input

CDXXI

Sample Output

True

References  

Regular expressions are a key concept in any programming language. A quick explanation with Python examples is available here. You could also go through the link below to read more about regular expressions in Python.  

https://developers.google.com/edu/python/regular-expressions

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:


Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4


Example 2:


Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
We often have to copy large volumes of information. Such operation can take up many computer resources. Therefore, in this problem you are advised to come up with a way to copy some part of a number array into another one, quickly.

More formally, you've got two arrays of integers *a*1,<=*a*2,<=...,<=*a**n* and *b*1,<=*b*2,<=...,<=*b**n* of length *n*. Also, you've got *m* queries of two types:
 1.  Copy the subsegment of array *a* of length *k*, starting from position *x*, into array *b*, starting from position *y*, that is, execute *b**y*<=+<=*q*<==<=*a**x*<=+<=*q* for all integer *q* (0<=≤<=*q*<=&lt;<=*k*). The given operation is correct — both subsegments do not touch unexistent elements. 1.  Determine the value in position *x* of array *b*, that is, find value *b**x*. 
For each query of the second type print the result — the value of the corresponding element of array *b*.

Input Specification:
The first line contains two space-separated integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=105) — the number of elements in the arrays and the number of queries, correspondingly. The second line contains an array of integers *a*1,<=*a*2,<=...,<=*a**n* (|*a**i*|<=≤<=109). The third line contains an array of integers *b*1,<=*b*2,<=...,<=*b**n* (|*b**i*|<=≤<=109).

Next *m* lines contain the descriptions of the queries. The *i*-th line first contains integer *t**i* — the type of the *i*-th query (1<=≤<=*t**i*<=≤<=2). If *t**i*<==<=1, then the *i*-th query means the copying operation. If *t**i*<==<=2, then the *i*-th query means taking the value in array *b*. If *t**i*<==<=1, then the query type is followed by three integers *x**i*,<=*y**i*,<=*k**i* (1<=≤<=*x**i*,<=*y**i*,<=*k**i*<=≤<=*n*) — the parameters of the copying query. If *t**i*<==<=2, then the query type is followed by integer *x**i* (1<=≤<=*x**i*<=≤<=*n*) — the position in array *b*.

All numbers in the lines are separated with single spaces. It is guaranteed that all the queries are correct, that is, the copying borders fit into the borders of arrays *a* and *b*.

Output Specification:
For each second type query print the result on a single line.

Demo Input:
['5 10\n1 2 0 -1 3\n3 1 5 -2 0\n2 5\n1 3 3 3\n2 5\n2 4\n2 1\n1 2 1 4\n2 1\n2 4\n1 4 2 1\n2 2\n']

Demo Output:
['0\n3\n-1\n3\n2\n3\n-1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya has written some permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$, so for all $1 \leq i \leq n$ it is true that $1 \leq p_i \leq n$ and all $p_1, p_2, \ldots, p_n$ are different. After that he wrote $n$ numbers $next_1, next_2, \ldots, next_n$. The number $next_i$ is equal to the minimal index $i < j \leq n$, such that $p_j > p_i$. If there is no such $j$ let's let's define as $next_i = n + 1$.

In the evening Vasya went home from school and due to rain, his notebook got wet. Now it is impossible to read some written numbers. Permutation and some values $next_i$ are completely lost! If for some $i$ the value $next_i$ is lost, let's say that $next_i = -1$.

You are given numbers $next_1, next_2, \ldots, next_n$ (maybe some of them are equal to $-1$). Help Vasya to find such permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$, that he can write it to the notebook and all numbers $next_i$, which are not equal to $-1$, will be correct. 


-----Input-----

The first line contains one integer $t$ — the number of test cases ($1 \leq t \leq 100\,000$).

Next $2 \cdot t$ lines contains the description of test cases,two lines for each. The first line contains one integer $n$ — the length of the permutation, written by Vasya ($1 \leq n \leq 500\,000$). The second line contains $n$ integers $next_1, next_2, \ldots, next_n$, separated by spaces ($next_i = -1$ or $i < next_i \leq n + 1$).

It is guaranteed, that the sum of $n$ in all test cases doesn't exceed $500\,000$.

In hacks you can only use one test case, so $T = 1$.


-----Output-----

Print $T$ lines, in $i$-th of them answer to the $i$-th test case.

If there is no such permutations $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$, that Vasya could write, print the only number $-1$.

In the other case print $n$ different integers $p_1, p_2, \ldots, p_n$, separated by spaces ($1 \leq p_i \leq n$). All defined values of $next_i$ which are not equal to $-1$ should be computed correctly $p_1, p_2, \ldots, p_n$ using defenition given in the statement of the problem. If there exists more than one solution you can find any of them.


-----Example-----
Input
6
3
2 3 4
2
3 3
3
-1 -1 -1
3
3 4 -1
1
2
4
4 -1 4 5

Output
1 2 3
2 1
2 1 3
-1
1
3 2 1 4



-----Note-----

In the first test case for permutation $p = [1, 2, 3]$ Vasya should write $next = [2, 3, 4]$, because each number in permutation is less than next. It's easy to see, that it is the only satisfying permutation.

In the third test case, any permutation can be the answer because all numbers $next_i$ are lost.

In the fourth test case, there is no satisfying permutation, so the answer is $-1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For two positive integers a and b, let g(a, b) = [gcd]
(a, b) + [lcm](a, b). 

For a positive integer N, let f(N) denote the minimum value of g(a, b) over all the pairs of positive integers (a, b) such that a+b = N.

Find out the number of ordered pairs (a, b) such that a+b = N and g(a, b) = f(N). 

------ Input Format ------ 

- The first line of input will contain an integer T — the number of test cases. The description of T test cases follows.
- The first and only line of each test case contains a positive integer N.

------ Output Format ------ 

For each test case, output the number of ordered pairs (a, b) such that a+b = N and g(a, b) = f(N).

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

$1 ≤ T ≤ 100$
$2 ≤ N ≤ 10^{9}$

----- Sample Input 1 ------ 
2
4
105
----- Sample Output 1 ------ 
3
14

----- explanation 1 ------ 
Test case $1$:
- For the pair $(1, 3)$, $g(1, 3) = gcd(1,3)+lcm(1,3)=1+3=4$.
- For the pair $(2, 2)$, $g(2, 2) = gcd(2,2)+lcm(2,2)=2+2=4$.
- For the pair $(3, 1)$, $g(3, 1) = gcd(3,1)+lcm(3,1)=1+3=4$.

Hence, $f(4) = 4$. There are three pairs $(a, b)$ satisfying $a+b = N$ and $g(a, b) = f(N)$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a permutation *p* of length *n*. Also you are given *m* foe pairs (*a**i*,<=*b**i*) (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*,<=*a**i*<=≠<=*b**i*). 

Your task is to count the number of different intervals (*x*,<=*y*) (1<=≤<=*x*<=≤<=*y*<=≤<=*n*) that do not contain any foe pairs. So you shouldn't count intervals (*x*,<=*y*) that contain at least one foe pair in it (the positions and order of the values from the foe pair are not important).

Consider some example: *p*<==<=[1,<=3,<=2,<=4] and foe pairs are {(3,<=2),<=(4,<=2)}. The interval (1,<=3) is incorrect because it contains a foe pair (3,<=2). The interval (1,<=4) is also incorrect because it contains two foe pairs (3,<=2) and (4,<=2). But the interval (1,<=2) is correct because it doesn't contain any foe pair.

Input Specification:
The first line contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=3·105) — the length of the permutation *p* and the number of foe pairs.

The second line contains *n* distinct integers *p**i* (1<=≤<=*p**i*<=≤<=*n*) — the elements of the permutation *p*.

Each of the next *m* lines contains two integers (*a**i*,<=*b**i*) (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*,<=*a**i*<=≠<=*b**i*) — the *i*-th foe pair. Note a foe pair can appear multiple times in the given list.

Output Specification:
Print the only integer *c* — the number of different intervals (*x*,<=*y*) that does not contain any foe pairs.

Note that the answer can be too large, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.

Demo Input:
['4 2\n1 3 2 4\n3 2\n2 4\n', '9 5\n9 7 2 3 1 4 6 5 8\n1 6\n4 5\n2 7\n7 2\n2 7\n']

Demo Output:
['5\n', '20\n']

Note:
In the first example the intervals from the answer are (1, 1), (1, 2), (2, 2), (3, 3) and (4, 4).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The most basic encryption method is to map a char to another char by a certain math rule.
Because every char has an ASCII value, we can manipulate this value with a simple math expression. 
For example 'a' + 1 would give us 'b', because 'a' value is 97 and 'b' value is 98.

You will need to write a method which does exactly that - 

get a string as text and an int as the rule of manipulation, and should return encrypted text.
for example:

encrypt("a",1) = "b"

 *Full ascii table is used on our question (256 chars) - so 0-255 are the valid values.*
 
Good luck.

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