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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
While Vasya finished eating his piece of pizza, the lesson has already started. For being late for the lesson, the teacher suggested Vasya to solve one interesting problem. Vasya has an array a and integer x. He should find the number of different ordered pairs of indexes (i, j) such that ai ≤ aj and there are exactly k integers y such that ai ≤ y ≤ aj and y is divisible by x.

In this problem it is meant that pair (i, j) is equal to (j, i) only if i is equal to j. For example pair (1, 2) is not the same as (2, 1).

## Input Format
The first line contains 3 integers n, x, k (1 ≤ n ≤ 105, 1 ≤ x ≤ 109, 0 ≤ k ≤ 109), where n is the size of the array a and x and k are numbers from the statement.

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

## Output Format
Print one integer — the answer to the problem.

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

## Note
In first sample there are only three suitable pairs of indexes — (1, 2), (2, 3), (3, 4).

In second sample there are four suitable pairs of indexes(1, 1), (2, 2), (3, 3), (4, 4).

In third sample every pair (i, j) is suitable, so the answer is 5 * 5 = 25.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 256.0 MB

# Problem
Petya was late for the lesson too. The teacher gave him an additional task. For some array a Petya should find the number of different ways to select non-empty subset of elements from it in such a way that their product is equal to a square of some integer.

Two ways are considered different if sets of indexes of elements chosen by these ways are different.

Since the answer can be very large, you should find the answer modulo 109 + 7.

## Input Format
First line contains one integer n (1 ≤ n ≤ 105) — the number of elements in the array.

Second line contains n integers ai (1 ≤ ai ≤ 70) — the elements of the array.

## Output Format
Print one integer — the number of different ways to choose some elements so that their product is a square of a certain integer modulo 109 + 7.

## Examples
```input
4
1 1 1 1
```
```output
15
```
-----
```input
4
2 2 2 2
```
```output
7
```
-----
```input
5
1 2 4 5 8
```
```output
7
```

## Note
In first sample product of elements chosen by any way is 1 and 1 = 12. So the answer is 24 - 1 = 15.

In second sample there are six different ways to choose elements so that their product is 4, and only one way so that their product is 16. So the answer is 6 + 1 = 7.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 256.0 MB

# Problem
At the Byteland State University marks are strings of the same length. Mark x is considered better than y if string y is lexicographically smaller than x.

Recently at the BSU was an important test work on which Vasya recived the mark a. It is very hard for the teacher to remember the exact mark of every student, but he knows the mark b, such that every student recieved mark strictly smaller than b.

Vasya isn't satisfied with his mark so he decided to improve it. He can swap characters in the string corresponding to his mark as many times as he like. Now he want to know only the number of different ways to improve his mark so that his teacher didn't notice something suspicious.

More formally: you are given two strings a, b of the same length and you need to figure out the number of different strings c such that:

1) c can be obtained from a by swapping some characters, in other words c is a permutation of a.

2) String a is lexicographically smaller than c.

3) String c is lexicographically smaller than b.

For two strings x and y of the same length it is true that x is lexicographically smaller than y if there exists such i, that x1 = y1, x2 = y2, ..., xi - 1 = yi - 1, xi < yi.

Since the answer can be very large, you need to find answer modulo 109 + 7.

## Input Format
First line contains string a, second line contains string b. Strings a, b consist of lowercase English letters. Their lengths are equal and don't exceed 106.

It is guaranteed that a is lexicographically smaller than b.

## Output Format
Print one integer  — the number of different strings satisfying the condition of the problem modulo 109 + 7.

## Examples
```input
abc
ddd
```
```output
5
```
-----
```input
abcdef
abcdeg
```
```output
0
```
-----
```input
abacaba
ubuduba
```
```output
64
```

## Note
In first sample from string abc can be obtained strings acb, bac, bca, cab, cba, all of them are larger than abc, but smaller than ddd. So the answer is 5.

In second sample any string obtained from abcdef is larger than abcdeg. So the answer is 0.

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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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.