vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Richik$Richik$ has just completed his engineering and has got a job in one of the firms at Sabrina$Sabrina$ which is ranked among the top seven islands in the world in terms of the pay scale. 
Since Richik$Richik$ has to travel a lot to reach the firm, the owner assigns him a number X$X$, and asks him to come to work only on the day which is a multiple of X$X$. Richik joins the firm on 1-st day but starts working from X-th day. Richik$Richik$ is paid exactly the same amount in Dollars as the day number. For example, if Richik$Richik$ has been assigned X=3$X = 3$, then he will be paid 3$3$ dollars and 6$6$ dollars on the 3rd$3rd$ and 6th$6th$ day on which he comes for work. 
On N−th$N-th$ day, the owner calls up Richik$Richik$ and asks him not to come to his firm anymore. Hence Richik$Richik$ demands his salary of all his working days together. Since it will take a lot of time to add, Richik$Richik$ asks help from people around him, let's see if you can help him out. 

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

-----Output:-----
For each testcase, output in a single line which is the salary which Richik$Richik$ demands. 

-----Constraints-----
- 1≤T≤1000$1 \leq T \leq 1000$
- 1≤X<=N≤107$1 \leq X<=N \leq 10^7$

-----Sample Input:-----
1
3 10

-----Sample Output:-----
18

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Valera had an undirected connected graph without self-loops and multiple edges consisting of *n* vertices. The graph had an interesting property: there were at most *k* edges adjacent to each of its vertices. For convenience, we will assume that the graph vertices were indexed by integers from 1 to *n*.

One day Valera counted the shortest distances from one of the graph vertices to all other ones and wrote them out in array *d*. Thus, element *d*[*i*] of the array shows the shortest distance from the vertex Valera chose to vertex number *i*.

Then something irreparable terrible happened. Valera lost the initial graph. However, he still has the array *d*. Help him restore the lost graph.

Input Specification:
The first line contains two space-separated integers *n* and *k* (1<=≤<=*k*<=&lt;<=*n*<=≤<=105). Number *n* shows the number of vertices in the original graph. Number *k* shows that at most *k* edges were adjacent to each vertex in the original graph.

The second line contains space-separated integers *d*[1],<=*d*[2],<=...,<=*d*[*n*] (0<=≤<=*d*[*i*]<=&lt;<=*n*). Number *d*[*i*] shows the shortest distance from the vertex Valera chose to the vertex number *i*.

Output Specification:
If Valera made a mistake in his notes and the required graph doesn't exist, print in the first line number -1. Otherwise, in the first line print integer *m* (0<=≤<=*m*<=≤<=106) — the number of edges in the found graph.

In each of the next *m* lines print two space-separated integers *a**i* and *b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*; *a**i*<=≠<=*b**i*), denoting the edge that connects vertices with numbers *a**i* and *b**i*. The graph shouldn't contain self-loops and multiple edges. If there are multiple possible answers, print any of them.

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

Demo Output:
['3\n1 2\n1 3\n3 2\n', '3\n1 3\n1 4\n2 3\n', '-1\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Captain Marmot wants to prepare a huge and important battle against his enemy, Captain Snake. For this battle he has *n* regiments, each consisting of 4 moles.

Initially, each mole *i* (1<=≤<=*i*<=≤<=4*n*) is placed at some position (*x**i*,<=*y**i*) in the Cartesian plane. Captain Marmot wants to move some moles to make the regiments compact, if it's possible.

Each mole *i* has a home placed at the position (*a**i*,<=*b**i*). Moving this mole one time means rotating his position point (*x**i*,<=*y**i*) 90 degrees counter-clockwise around it's home point (*a**i*,<=*b**i*).

A regiment is compact only if the position points of the 4 moles form a square with non-zero area.

Help Captain Marmot to find out for each regiment the minimal number of moves required to make that regiment compact, if it's possible.

Input Specification:
The first line contains one integer *n* (1<=≤<=*n*<=≤<=100), the number of regiments.

The next 4*n* lines contain 4 integers *x**i*, *y**i*, *a**i*, *b**i* (<=-<=104<=≤<=*x**i*,<=*y**i*,<=*a**i*,<=*b**i*<=≤<=104).

Output Specification:
Print *n* lines to the standard output. If the regiment *i* can be made compact, the *i*-th line should contain one integer, the minimal number of required moves. Otherwise, on the *i*-th line print "-1" (without quotes).

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

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

Note:
In the first regiment we can move once the second or the third mole.

We can't make the second regiment compact.

In the third regiment, from the last 3 moles we can move once one and twice another one.

In the fourth regiment, we can move twice the first mole and once the third mole.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One evening Rainbow Dash and Fluttershy have come up with a game. Since the ponies are friends, they have decided not to compete in the game but to pursue a common goal. 

The game starts on a square flat grid, which initially has the outline borders built up. Rainbow Dash and Fluttershy have flat square blocks with size $1\times1$, Rainbow Dash has an infinite amount of light blue blocks, Fluttershy has an infinite amount of yellow blocks. 

The blocks are placed according to the following rule: each newly placed block must touch the built on the previous turns figure by a side (note that the outline borders of the grid are built initially). At each turn, one pony can place any number of blocks of her color according to the game rules.

Rainbow and Fluttershy have found out that they can build patterns on the grid of the game that way. They have decided to start with something simple, so they made up their mind to place the blocks to form a chess coloring. Rainbow Dash is well-known for her speed, so she is interested in the minimum number of turns she and Fluttershy need to do to get a chess coloring, covering the whole grid with blocks. Please help her find that number!

Since the ponies can play many times on different boards, Rainbow Dash asks you to find the minimum numbers of turns for several grids of the games.

The chess coloring in two colors is the one in which each square is neighbor by side only with squares of different colors.


-----Input-----

The first line contains a single integer $T$ ($1 \le T \le 100$): the number of grids of the games. 

Each of the next $T$ lines contains a single integer $n$ ($1 \le n \le 10^9$): the size of the side of the grid of the game. 


-----Output-----

For each grid of the game print the minimum number of turns required to build a chess coloring pattern out of blocks on it.


-----Example-----
Input
2
3
4

Output
2
3



-----Note-----

For $3\times3$ grid ponies can make two following moves: [Image]

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

Time Limit: 0 seconds

Memory Limit: 64 megabytes

Problem Description:
Tomorrow Peter has a Biology exam. He does not like this subject much, but *d* days ago he learnt that he would have to take this exam. Peter's strict parents made him prepare for the exam immediately, for this purpose he has to study not less than *minTime**i* and not more than *maxTime**i* hours per each *i*-th day. Moreover, they warned Peter that a day before the exam they would check how he has followed their instructions.

So, today is the day when Peter's parents ask him to show the timetable of his preparatory studies. But the boy has counted only the sum of hours *sumTime* spent him on preparation, and now he wants to know if he can show his parents a timetable *sсhedule* with *d* numbers, where each number *sсhedule**i* stands for the time in hours spent by Peter each *i*-th day on biology studies, and satisfying the limitations imposed by his parents, and at the same time the sum total of all *schedule**i* should equal to *sumTime*.

Input Specification:
The first input line contains two integer numbers *d*,<=*sumTime* (1<=≤<=*d*<=≤<=30,<=0<=≤<=*sumTime*<=≤<=240) — the amount of days, during which Peter studied, and the total amount of hours, spent on preparation. Each of the following *d* lines contains two integer numbers *minTime**i*,<=*maxTime**i* (0<=≤<=*minTime**i*<=≤<=*maxTime**i*<=≤<=8), separated by a space — minimum and maximum amount of hours that Peter could spent in the *i*-th day.

Output Specification:
In the first line print YES, and in the second line print *d* numbers (separated by a space), each of the numbers — amount of hours, spent by Peter on preparation in the corresponding day, if he followed his parents' instructions; or print NO in the unique line. If there are many solutions, print any of them.

Demo Input:
['1 48\n5 7\n', '2 5\n0 1\n3 5\n']

Demo Output:
['NO\n', 'YES\n1 4 ']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
This problem uses a simplified network topology model, please read the problem statement carefully and use it as a formal document as you develop the solution.

Polycarpus continues working as a system administrator in a large corporation. The computer network of this corporation consists of *n* computers, some of them are connected by a cable. The computers are indexed by integers from 1 to *n*. It's known that any two computers connected by cable directly or through other computers

Polycarpus decided to find out the network's topology. A network topology is the way of describing the network configuration, the scheme that shows the location and the connections of network devices.

Polycarpus knows three main network topologies: bus, ring and star. A bus is the topology that represents a shared cable with all computers connected with it. In the ring topology the cable connects each computer only with two other ones. A star is the topology where all computers of a network are connected to the single central node.

Let's represent each of these network topologies as a connected non-directed graph. A bus is a connected graph that is the only path, that is, the graph where all nodes are connected with two other ones except for some two nodes that are the beginning and the end of the path. A ring is a connected graph, where all nodes are connected with two other ones. A star is a connected graph, where a single central node is singled out and connected with all other nodes. For clarifications, see the picture.

You've got a connected non-directed graph that characterizes the computer network in Polycarpus' corporation. Help him find out, which topology type the given network is. If that is impossible to do, say that the network's topology is unknown.

Input Specification:
The first line contains two space-separated integers *n* and *m* (4<=≤<=*n*<=≤<=105; 3<=≤<=*m*<=≤<=105) — the number of nodes and edges in the graph, correspondingly. Next *m* lines contain the description of the graph's edges. The *i*-th line contains a space-separated pair of integers *x**i*, *y**i* (1<=≤<=*x**i*,<=*y**i*<=≤<=*n*) — the numbers of nodes that are connected by the *i*-the edge.

It is guaranteed that the given graph is connected. There is at most one edge between any two nodes. No edge connects a node with itself.

Output Specification:
In a single line print the network topology name of the given graph. If the answer is the bus, print "bus topology" (without the quotes), if the answer is the ring, print "ring topology" (without the quotes), if the answer is the star, print "star topology" (without the quotes). If no answer fits, print "unknown topology" (without the quotes).

Demo Input:
['4 3\n1 2\n2 3\n3 4\n', '4 4\n1 2\n2 3\n3 4\n4 1\n', '4 3\n1 2\n1 3\n1 4\n', '4 4\n1 2\n2 3\n3 1\n1 4\n']

Demo Output:
['bus topology\n', 'ring topology\n', 'star topology\n', 'unknown topology\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's assume that p and q are strings of positive length, called the container and the key correspondingly, string q only consists of characters 0 and 1. Let's take a look at a simple algorithm that extracts message s from the given container p:
    
    
      
    i = 0;  
    j = 0;  
    s = <>;  
    while i is less than the length of the string p  
    {  
        if q[j] == 1, then add to the right of string s character p[i];  
        increase variables i, j by one;  
        if the value of the variable j equals the length of the string q, then j = 0;   
    }  
    

In the given pseudocode i, j are integer variables, s is a string, '=' is an assignment operator, '==' is a comparison operation, '[]' is the operation of obtaining the string character with the preset index, '<>' is an empty string. We suppose that in all strings the characters are numbered starting from zero. 

We understand that implementing such algorithm is quite easy, so your task is going to be slightly different. You need to construct the lexicographically minimum key of length k, such that when it is used, the algorithm given above extracts message s from container p (otherwise find out that such key doesn't exist).

Input

The first two lines of the input are non-empty strings p and s (1 ≤ |p| ≤ 106, 1 ≤ |s| ≤ 200), describing the container and the message, correspondingly. The strings can contain any characters with the ASCII codes from 32 to 126, inclusive.

The third line contains a single integer k (1 ≤ k ≤ 2000) — the key's length.

Output

Print the required key (string of length k, consisting only of characters 0 and 1). If the key doesn't exist, print the single character 0.

Examples

Input

abacaba
aba
6


Output

100001


Input

abacaba
aba
3


Output

0

Note

String x = x1x2... xp is lexicographically smaller than string y = y1y2... yq, if either p < q and x1 = y1, x2 = y2, ... , xp = yp, or there exists such integer r (0 ≤ r < min(p, q)) that x1 = y1, x2 = y2, ... , xr = yr and xr + 1 < yr + 1. Symbols are compared according to their ASCII codes.

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

Time Limit: 2 seconds

Memory Limit: 64 megabytes

Problem Description:
Bob likes to draw camels: with a single hump, two humps, three humps, etc. He draws a camel by connecting points on a coordinate plane. Now he's drawing camels with *t* humps, representing them as polylines in the plane. Each polyline consists of *n* vertices with coordinates (*x*1,<=*y*1), (*x*2,<=*y*2), ..., (*x**n*,<=*y**n*). The first vertex has a coordinate *x*1<==<=1, the second — *x*2<==<=2, etc. Coordinates *y**i* might be any, but should satisfy the following conditions:
 -  there should be *t* humps precisely, i.e. such indexes *j* (2<=≤<=*j*<=≤<=*n*<=-<=1), so that *y**j*<=-<=1<=&lt;<=*y**j*<=&gt;<=*y**j*<=+<=1, -  there should be precisely *t*<=-<=1 such indexes *j* (2<=≤<=*j*<=≤<=*n*<=-<=1), so that *y**j*<=-<=1<=&gt;<=*y**j*<=&lt;<=*y**j*<=+<=1, -  no segment of a polyline should be parallel to the *Ox*-axis, -  all *y**i* are integers between 1 and 4. 
For a series of his drawings of camels with *t* humps Bob wants to buy a notebook, but he doesn't know how many pages he will need. Output the amount of different polylines that can be drawn to represent camels with *t* humps for a given number *n*.

Input Specification:
The first line contains a pair of integers *n* and *t* (3<=≤<=*n*<=≤<=20, 1<=≤<=*t*<=≤<=10).

Output Specification:
Output the required amount of camels with *t* humps.

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

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

Note:
In the first sample test sequences of *y*-coordinates for six camels are: 123421, 123431, 123432, 124321, 134321 и 234321 (each digit corresponds to one value of *y*<sub class="lower-index">*i*</sub>).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For given two sequneces $A = \\{a_0, a_1, ..., a_{n-1}\\}$ and $B = \\{b_0, b_1, ..., b_{m-1}\\}$, determine whether all elements of $B$ are included in $A$. Note that, elements of $A$ and $B$ are sorted by ascending order respectively.

Constraints

* $1 \leq n, m \leq 200,000$
* $-1,000,000,000 \leq a_0 < a_1 < ... < a_{n-1} \leq 1,000,000,000$
* $-1,000,000,000 \leq b_0 < b_1 < ... < b_{m-1} \leq 1,000,000,000$

Input

The input is given in the following format.


$n$
$a_0 \; a_1 \; ,..., \; a_{n-1}$
$m$
$b_0 \; b_1 \; ,..., \; b_{m-1}$


The number of elements in $A$ and its elements $a_i$ are given in the first and second lines respectively. The number of elements in $B$ and its elements $b_i$ are given in the third and fourth lines respectively.

Output

Print 1, if $A$ contains all elements of $B$, otherwise 0.

Examples

Input

4
1 2 3 4
2
2 4


Output

1


Input

4
1 2 3 4
3
1 2 5


Output

0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given integers N and M.
Consider a sequence a of length N consisting of positive integers such that a_1 + a_2 + ... + a_N = M. Find the maximum possible value of the greatest common divisor of a_1, a_2, ..., a_N.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 10^5
 - N \leq M \leq 10^9

-----Input-----
Input is given from Standard Input in the following format:
N M

-----Output-----
Print the maximum possible value of the greatest common divisor of a sequence a_1, a_2, ..., a_N that satisfies the condition.

-----Sample Input-----
3 14

-----Sample Output-----
2

Consider the sequence (a_1, a_2, a_3) = (2, 4, 8). Their greatest common divisor is 2, and this is the maximum value.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Mad scientist Mike does not use slow hard disks. His modification of a hard drive has not one, but *n* different heads that can read data in parallel.

When viewed from the side, Mike's hard drive is an endless array of tracks. The tracks of the array are numbered from left to right with integers, starting with 1. In the initial state the *i*-th reading head is above the track number *h**i*. For each of the reading heads, the hard drive's firmware can move the head exactly one track to the right or to the left, or leave it on the current track. During the operation each head's movement does not affect the movement of the other heads: the heads can change their relative order; there can be multiple reading heads above any of the tracks. A track is considered read if at least one head has visited this track. In particular, all of the tracks numbered *h*1, *h*2, ..., *h**n* have been read at the beginning of the operation.

Mike needs to read the data on *m* distinct tracks with numbers *p*1, *p*2, ..., *p**m*. Determine the minimum time the hard drive firmware needs to move the heads and read all the given tracks. Note that an arbitrary number of other tracks can also be read.

Input Specification:
The first line of the input contains two space-separated integers *n*, *m* (1<=≤<=*n*,<=*m*<=≤<=105) — the number of disk heads and the number of tracks to read, accordingly. The second line contains *n* distinct integers *h**i* in ascending order (1<=≤<=*h**i*<=≤<=1010, *h**i*<=&lt;<=*h**i*<=+<=1) — the initial positions of the heads. The third line contains *m* distinct integers *p**i* in ascending order (1<=≤<=*p**i*<=≤<=1010, *p**i*<=&lt;<=*p**i*<=+<=1) - the numbers of tracks to read.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is recommended to use the cin, cout streams or the %I64d specifier.

Output Specification:
Print a single number — the minimum time required, in seconds, to read all the needed tracks.

Demo Input:
['3 4\n2 5 6\n1 3 6 8\n', '3 3\n1 2 3\n1 2 3\n', '1 2\n165\n142 200\n']

Demo Output:
['2\n', '0\n', '81\n']

Note:
The first test coincides with the figure. In this case the given tracks can be read in 2 seconds in the following way: 
 1.  during the first second move the 1-st head to the left and let it stay there; 1.  move the second head to the left twice; 1.  move the third head to the right twice (note that the 6-th track has already been read at the beginning). 
One cannot read the tracks in 1 second as the 3-rd head is at distance 2 from the 8-th track.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the year 2020, a race of atomically energized cars will be held. Unlike today’s car races, fueling is not a concern of racing teams. Cars can run throughout the course without any refueling. Instead, the critical factor is tire (tyre). Teams should carefully plan where to change tires of their cars.

The race is a road race having n checkpoints in the course. Their distances from the start are a1, a2, ... , and an (in kilometers). The n-th checkpoint is the goal. At the i-th checkpoint (i < n), tires of a car can be changed. Of course, a team can choose whether to change or not to change tires at each checkpoint. It takes b seconds to change tires (including overhead for braking and accelerating). There is no time loss at a checkpoint if a team chooses not to change tires.

A car cannot run fast for a while after a tire change, because the temperature of tires is lower than the designed optimum. After running long without any tire changes, on the other hand, a car cannot run fast because worn tires cannot grip the road surface well. The time to run an interval of one kilometer from x to x + 1 is given by the following expression (in seconds). Here x is a nonnegative integer denoting the distance (in kilometers) from the latest checkpoint where tires are changed (or the start). r, v, e and f are given constants.


1/(v - e × (x - r)) (if x ≥ r)
1/(v - f × (r - x)) (if x < r)


Your mission is to write a program to determine the best strategy of tire changes which minimizes the total time to the goal.



Input

The input consists of multiple datasets each corresponding to a race situation. The format of a dataset is as follows.


n
a1 a2 . . . an
b
r v e f


The meaning of each of the input items is given in the problem statement. If an input line contains two or more input items, they are separated by a space.

n is a positive integer not exceeding 100. Each of a1, a2, ... , and an is a positive integer satisfying 0 < a1 < a2 < . . . < an ≤ 10000. b is a positive decimal fraction not exceeding 100.0. r is a nonnegative integer satisfying 0 ≤ r ≤ an - 1. Each of v, e and f is a positive decimal fraction. You can assume that v - e × (an - 1 - r) ≥ 0.01 and v - f × r ≥ 0.01.

The end of the input is indicated by a line with a single zero.

Output

For each dataset in the input, one line containing a decimal fraction should be output. The decimal fraction should give the elapsed time at the goal (in seconds) when the best strategy is taken. An output line should not contain extra characters such as spaces.

The answer should not have an error greater than 0.001. You may output any number of digits after the decimal point, provided that the above accuracy condition is satisfied.

Example

Input

2
2 3
1.0
1 1.0 0.1 0.3
5
5 10 15 20 25
0.15
1 1.0 0.04 0.5
10
1783 3640 3991 4623 5465 5481 6369 6533 6865 8425
4.172
72 59.4705 0.0052834 0.0611224
0


Output

3.5397
31.9249
168.6682

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