apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.5 seconds
Memory limit: 256.0 MB

# Problem
Vasya and Petya were tired of studying so they decided to play a game. Before the game begins Vasya looks at array a consisting of n integers. As soon as he remembers all elements of a the game begins. Vasya closes his eyes and Petya does q actions of one of two types:

1) Petya says 4 integers l1, r1, l2, r2 — boundaries of two non-intersecting segments. After that he swaps one random element from the [l1, r1] segment with another random element from the [l2, r2] segment.

2) Petya asks Vasya the sum of the elements of a in the [l, r] segment.

Vasya is a mathematician so he answers Petya the mathematical expectation of the sum of the elements in the segment.

Your task is to write a program which will answer the second type questions as Vasya would do it. In other words your program should print the mathematical expectation of the sum of the elements of a in the [l, r] segment for every second type query.

## Input Format
The first line contains two integers n, q (2 ≤ n ≤ 105, 1 ≤ q ≤ 105)  — the number of elements in the array and the number of queries you need to handle.

The second line contains n integers ai (1 ≤ ai ≤ 109)  — elements of the array.

The next q lines contain Petya's actions of type 1 or 2.

If it is a type 1 action then the line contains 5 integers 1, l1, r1, l2, r2 (1 ≤ l1 ≤ r1 ≤ n, 1 ≤ l2 ≤ r2 ≤ n).

If it is a type 2 query then the line contains 3 integers 2, l, r (1 ≤ l ≤ r ≤ n).

It is guaranteed that there is at least one type 2 query and segments [l1, r1], [l2, r2] don't have common elements.

## Output Format
For each type 2 query print one real number — the mathematical expectation of the sum of elements in the segment.

Your answer will be considered correct if its absolute or relative error doesn't exceed 10 - 4  — formally, the answer is correct if $${ \operatorname* { m i n } } ( | x - y |, { \frac { | x - y | } { x } } ) \leq 1 0 ^ { - 4 }$$ where x is jury's answer and y is yours.

## Examples
```input
4 4
1 1 2 2
1 2 2 3 3
2 1 2
1 1 2 3 4
2 1 2
```
```output
3.0000000
3.0000000
```
-----
```input
10 5
1 1 1 1 1 2 2 2 2 2
1 1 5 6 10
2 1 5
1 1 5 6 10
1 1 5 6 10
2 6 10
```
```output
6.0000000
8.0400000
```
-----
```input
10 10
1 2 3 4 5 6 7 8 9 10
1 1 5 6 10
1 1 5 6 10
2 1 5
1 1 3 6 9
2 1 3
1 5 7 8 10
1 1 1 10 10
2 1 5
2 7 10
2 1 10
```
```output
23.0000000
14.0000000
28.0133333
21.5733333
55.0000000
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You have n distinct points on a plane, none of them lie on OY axis. Check that there is a point after removal of which the remaining points are located on one side of the OY axis.

## Input Format
The first line contains a single positive integer n (2 ≤ n ≤ 105).

The following n lines contain coordinates of the points. The i-th of these lines contains two single integers xi and yi (|xi|, |yi| ≤ 109, xi ≠ 0). No two points coincide.

## Output Format
Print "Yes" if there is such a point, "No" — otherwise.

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

## Examples
```input
3
1 1
-1 -1
2 -1
```
```output
Yes
```
-----
```input
4
1 1
2 2
-1 1
-2 2
```
```output
No
```
-----
```input
3
1 2
2 1
4 60
```
```output
Yes
```

## Note
In the first example the second point can be removed.

In the second example there is no suitable for the condition point.

In the third example any point can be removed.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You have a fraction $${ \frac { a } { b } }$$. You need to find the first occurrence of digit c into decimal notation of the fraction after decimal point.

## Input Format
The first contains three single positive integers a, b, c (1 ≤ a < b ≤ 105, 0 ≤ c ≤ 9).

## Output Format
Print position of the first occurrence of digit c into the fraction. Positions are numbered from 1 after decimal point. It there is no such position, print -1.

## Examples
```input
1 2 0
```
```output
2
```
-----
```input
2 3 7
```
```output
-1
```

## Note
The fraction in the first example has the following decimal notation: $${ \frac { 1 } { 2 } } = 0. 5 0 0 ( 0 )$$. The first zero stands on second position.

The fraction in the second example has the following decimal notation: $${ \frac { 2 } { 3 } } = 0. 6 6 6 ( 6 )$$. There is no digit 7 in decimal notation of the fraction.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a permutation p of length n. Remove one element from permutation to make the number of records the maximum possible.

We remind that in a sequence of numbers a1, a2, ..., ak the element ai is a record if for every integer j (1 ≤ j < i) the following holds: aj < ai.

## Input Format
The first line contains the only integer n (1 ≤ n ≤ 105) — the length of the permutation.

The second line contains n integers p1, p2, ..., pn (1 ≤ pi ≤ n) — the permutation. All the integers are distinct.

## Output Format
Print the only integer — the element that should be removed to make the number of records the maximum possible. If there are multiple such elements, print the smallest one.

## Examples
```input
1
1
```
```output
1
```
-----
```input
5
5 1 2 3 4
```
```output
5
```

## Note
In the first example the only element can be removed.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Count the number of distinct sequences a1, a2, ..., an (1 ≤ ai) consisting of positive integers such that gcd(a1, a2, ..., an) = x and $$\sum_{i=1}^{n}a_{i}=y$$. As this number could be large, print the answer modulo 109 + 7.

gcd here means the greatest common divisor.

## Input Format
The only line contains two positive integers x and y (1 ≤ x, y ≤ 109).

## Output Format
Print the number of such sequences modulo 109 + 7.

## Examples
```input
3 9
```
```output
3
```
-----
```input
5 8
```
```output
0
```

## Note
There are three suitable sequences in the first test: (3, 3, 3), (3, 6), (6, 3).

There are no suitable sequences in the second test.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Vasya wrote down two strings s of length n and t of length m consisting of small English letters 'a' and 'b'. What is more, he knows that string t has a form "abab...", namely there are letters 'a' on odd positions and letters 'b' on even positions.

Suddenly in the morning, Vasya found that somebody spoiled his string. Some letters of the string s were replaced by character '?'.

Let's call a sequence of positions i, i + 1, ..., i + m - 1 as occurrence of string t in s, if 1 ≤ i ≤ n - m + 1 and t1 = si, t2 = si + 1, ..., tm = si + m - 1.

The boy defines the beauty of the string s as maximum number of disjoint occurrences of string t in s. Vasya can replace some letters '?' with 'a' or 'b' (letters on different positions can be replaced with different letter). Vasya wants to make some replacements in such a way that beauty of string s is maximum possible. From all such options, he wants to choose one with the minimum number of replacements. Find the number of replacements he should make.

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 105) — the length of s.

The second line contains the string s of length n. It contains small English letters 'a', 'b' and characters '?' only.

The third line contains a single integer m (1 ≤ m ≤ 105) — the length of t. The string t contains letters 'a' on odd positions and 'b' on even positions.

## Output Format
Print the only integer — the minimum number of replacements Vasya has to perform to make the beauty of string s the maximum possible.

## Examples
```input
5
bb?a?
1
```
```output
2
```
-----
```input
9
ab??ab???
3
```
```output
2
```

## Note
In the first sample string t has a form 'a'. The only optimal option is to replace all characters '?' by 'a'.

In the second sample using two replacements we can make string equal to "aba?aba??". It is impossible to get more than two occurrences.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Eleven wants to choose a new name for herself. As a bunch of geeks, her friends suggested an algorithm to choose a name for her. Eleven wants her name to have exactly n characters.

Her friend suggested that her name should only consist of uppercase and lowercase letters 'O'. More precisely, they suggested that the i-th letter of her name should be 'O' (uppercase) if i is a member of Fibonacci sequence, and 'o' (lowercase) otherwise. The letters in the name are numbered from 1 to n. Fibonacci sequence is the sequence f where

- f1 = 1,
- f2 = 1,
- fn = fn - 2 + fn - 1 (n > 2).

As her friends are too young to know what Fibonacci sequence is, they asked you to help Eleven determine her new name.

## Input Format
The first and only line of input contains an integer n (1 ≤ n ≤ 1000).

## Output Format
Print Eleven's new name on the first and only line of output.

## Examples
```input
8
```
```output
OOOoOooO
```
-----
```input
15
```
```output
OOOoOooOooooOoo
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
As the guys fried the radio station facilities, the school principal gave them tasks as a punishment. Dustin's task was to add comments to nginx configuration for school's website. The school has n servers. Each server has a name and an ip (names aren't necessarily unique, but ips are). Dustin knows the ip and name of each server. For simplicity, we'll assume that an nginx command is of form "command ip;" where command is a string consisting of English lowercase letter only, and ip is the ip of one of school servers.

Each ip is of form "a.b.c.d" where a, b, c and d are non-negative integers less than or equal to 255 (with no leading zeros). The nginx configuration file Dustin has to add comments to has m commands. Nobody ever memorizes the ips of servers, so to understand the configuration better, Dustin has to comment the name of server that the ip belongs to at the end of each line (after each command). More formally, if a line is "command ip;" Dustin has to replace it with "command ip; #name" where name is the name of the server with ip equal to ip.

Dustin doesn't know anything about nginx, so he panicked again and his friends asked you to do his task for him.

## Input Format
The first line of input contains two integers n and m (1 ≤ n, m ≤ 1000).

The next n lines contain the names and ips of the servers. Each line contains a string name, name of the server and a string ip, ip of the server, separated by space (1 ≤ |name| ≤ 10, name only consists of English lowercase letters). It is guaranteed that all ip are distinct.

The next m lines contain the commands in the configuration file. Each line is of form "command ip;" (1 ≤ |command| ≤ 10, command only consists of English lowercase letters). It is guaranteed that ip belongs to one of the n school servers.

## Output Format
Print m lines, the commands in the configuration file after Dustin did his task.

## Examples
```input
2 2
main 192.168.0.2
replica 192.168.0.1
block 192.168.0.1;
proxy 192.168.0.2;
```
```output
block 192.168.0.1; #replica
proxy 192.168.0.2; #main
```
-----
```input
3 5
google 8.8.8.8
codeforces 212.193.33.27
server 138.197.64.57
redirect 138.197.64.57;
block 8.8.8.8;
cf 212.193.33.27;
unblock 8.8.8.8;
check 138.197.64.57;
```
```output
redirect 138.197.64.57; #server
block 8.8.8.8; #google
cf 212.193.33.27; #codeforces
unblock 8.8.8.8; #google
check 138.197.64.57; #server
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Завтра у хоккейной команды, которой руководит Евгений, важный матч. Евгению нужно выбрать шесть игроков, которые выйдут на лед в стартовом составе: один вратарь, два защитника и три нападающих.

Так как это стартовый состав, Евгения больше волнует, насколько красива будет команда на льду, чем способности игроков. А именно, Евгений хочет выбрать такой стартовый состав, чтобы номера любых двух игроков из стартового состава отличались не более, чем в два раза. Например, игроки с номерами 13, 14, 10, 18, 15 и 20 устроят Евгения, а если, например, на лед выйдут игроки с номерами 8 и 17, то это не устроит Евгения.

Про каждого из игроков вам известно, на какой позиции он играет (вратарь, защитник или нападающий), а также его номер. В хоккее номера игроков не обязательно идут подряд. Посчитайте число различных стартовых составов из одного вратаря, двух защитников и трех нападающих, которые может выбрать Евгений, чтобы выполнялось его условие красоты.

## Input Format
Первая строка содержит три целых числа g, d и f (1 ≤ g ≤ 1 000, 1 ≤ d ≤ 1 000, 1 ≤ f ≤ 1 000) — число вратарей, защитников и нападающих в команде Евгения.

Вторая строка содержит g целых чисел, каждое в пределах от 1 до 100 000 — номера вратарей.

Третья строка содержит d целых чисел, каждое в пределах от 1 до 100 000 — номера защитников.

Четвертая строка содержит f целых чисел, каждое в пределах от 1 до 100 000 — номера нападающих.

Гарантируется, что общее количество игроков не превосходит 1 000, т. е. g + d + f ≤ 1 000. Все g + d + f номеров игроков различны.

## Output Format
Выведите одно целое число — количество возможных стартовых составов.

## Examples
```input
1 2 3
15
10 19
20 11 13
```
```output
1
```
-----
```input
2 3 4
16 40
20 12 19
13 21 11 10
```
```output
6
```

## Note
В первом примере всего один вариант для выбора состава, который удовлетворяет описанным условиям, поэтому ответ 1.

Во втором примере подходят следующие игровые сочетания (в порядке вратарь-защитник-защитник-нападающий-нападающий-нападающий):

- 16 20 12 13 21 11
- 16 20 12 13 11 10
- 16 20 19 13 21 11
- 16 20 19 13 11 10
- 16 12 19 13 21 11
- 16 12 19 13 11 10

Таким образом, ответ на этот пример — 6.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Герой Аркадий находится на узкой полоске земли, разделенной на n зон, пронумерованных от 1 до n. Из i-й зоны можно пройти лишь в (i - 1)-ю зону и в (i + 1)-ю зону, если они существуют. При этом между каждой парой соседних зон находятся пограничные врата, которые могут быть разных цветов, цвет врат между i-й и (i + 1)-й зоной равен gi.

Аркадий может пройти пограничные врата некоторого цвета, только если он перед этим побывал в одном из шатров хранителей ключей этого цвета и взял ключ. В каждой зоне находится ровно один шатер хранителя ключей некоторого цвета, цвет шатра в i-й зоне равен ki. После посещения шатра определенного цвета Аркадий может неограниченное число раз проходить через любые врата этого цвета.

На проход через одни врата Аркадий тратит один ход, на посещение шатра и другие перемещения ходы не требуются. За какое минимальное число ходов Аркадий может попасть из зоны a в зону b, если изначально у него нет никаких ключей?

## Input Format
Первая строка содержит три целых числа n, a, b (2 ≤ n ≤ 100 000, 1 ≤ a, b ≤ n, a ≠ b) — число зон, номер начальной зоны и номер конечной зоны, соответственно.

Вторая строка содержит n - 1 целое число g1, g2, ..., gn - 1 (1 ≤ gi ≤ 100 000), где gi означает цвет пограничных врат между зонами i и i + 1.

Третья строка содержит n целых чисел k1, k2, ..., kn (1 ≤ ki ≤ 100 000), где ki означает цвет шатра хранителя ключей в i-й зоне.

## Output Format
Если Аркадий не может попасть из зоны a в зону b, не имея изначально ключей, выведите -1.

Иначе выведите минимальное количество ходов, которое потребуется Аркадию.

## Examples
```input
5 4 1
3 1 1 2
7 1 2 1 3
```
```output
7
```
-----
```input
5 1 5
4 3 2 1
4 3 2 5 5
```
```output
-1
```

## Note
В первом примере, чтобы попасть из зоны 4 в зону 1, Аркадию нужно сначала взять ключ цвета 1, пройти в зону 3, там взять ключ цвета 2 и пройти обратно в зону 4 и затем в зону 5, взять там ключ цвета 3 и дойти до зоны 1 за четыре хода.

Во втором примере Аркадий может дойти лишь до четвертой зоны, так как шатров хранителей ключей цвета 1 нет совсем.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
When Igor K. was a freshman, his professor strictly urged him, as well as all other freshmen, to solve programming Olympiads. One day a problem called "Flags" from a website called Timmy's Online Judge caught his attention. In the problem one had to find the number of three-colored flags that would satisfy the condition... actually, it doesn't matter. Igor K. quickly found the formula and got the so passionately desired Accepted.

However, the professor wasn't very much impressed. He decided that the problem represented on Timmy's Online Judge was very dull and simple: it only had three possible colors of flag stripes and only two limitations. He suggested a complicated task to Igor K. and the fellow failed to solve it. Of course, we won't tell anybody that the professor couldn't solve it as well.

And how about you? Can you solve the problem?

The flags consist of one or several parallel stripes of similar width. The stripes can be one of the following colors: white, black, red or yellow. You should find the number of different flags with the number of stripes from L to R, if:

- a flag cannot have adjacent stripes of one color;
- a flag cannot have adjacent white and yellow stripes;
- a flag cannot have adjacent red and black stripes;
- a flag cannot have the combination of black, white and red stripes following one after another in this or reverse order;
- symmetrical flags (as, for example, a WB and a BW flag, where W and B stand for the white and black colors) are considered the same.

## Input Format
The only line contains two integers L and R (1 ≤ L ≤ R ≤ 109). They are the lower and upper borders of the number of stripes on the flag.

## Output Format
Print a single number — the number of different flags that would satisfy the condition of the problem and would have from L to R stripes, modulo 1000000007.

## Examples
```input
3 4
```
```output
23
```
-----
```input
5 6
```
```output
64
```

## Note
In the first test the following flags exist (they are listed in the lexicographical order, the letters B, R, W, Y stand for Black, Red, White and Yellow correspondingly):

3 stripes: BWB, BYB, BYR, RWR, RYR, WBW, WBY, WRW, WRY, YBY, YRY (overall 11 flags).

4 stripes: BWBW, BWBY, BYBW, BYBY, BYRW, BYRY, RWRW, RWRY, RYBW, RYBY, RYRW, RYRY (12 flags).

That's why the answer to test 1 is equal to 11 + 12 = 23.

Now solve the problem and return the code.