vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Your dog Spot is let loose in the park. Well, relatively loose – he is tied to a post with a leash, limiting his movements. Spread around the park are various squeaky toys and other dog paraphernalia, which Spot happily goes after when he sees them. When he gets to a toy he will chew at it for a while until it has become defunct, at which point he will go after the next toy, which looks much squeakier.

This is all very well, but there are obstacles to Spot’s joyful canine play: trees. In the park there are several trees, and if Spot walks around a tree his leash gets wrapped around the tree, making his movements more limited. Being a dog, with pressing squeaky matters to attend to, Spot does not really have time to take things such as trees into account, and always goes directly in a straight line for his next toy. If he can’t get to his next toy because he has run out of leash, Spot will start barking uncontrollably (as no doubt any of us would) and you have to help him. How long would Spot’s leash have to be in order for him to run out of toys before he runs out of leash?

For practical purposes, you may assume that (when seen from above) Spot, his toys, and the trees are points, and that the post that the leash is tied to will not hinder Spot’s movements in any way. After having finished chewing a toy, Spot always goes for the most shiny unchewed toy. The post to which Spot’s leash is tied is located at coordinates $(0,0)$, and this is also where Spot is initially located.

-----Input-----
The first line of input consists of two integers $n$ and $m$, where $1 \le n \le 50$ is the number of toys in the park and $0 \le m \le 50$ is the number of trees in the park. Then follow $n$ lines, each containing two integers $x$, $y$ giving the coordinates of a toy. The toys are listed in decreasing order of shininess. This is followed by $m$ lines, each containing two integers $x$, $y$, indicating that there is a tree at those coordinates.

Each coordinate is bounded by 10000 in absolute value. The toys, the trees and the post are all in different positions, and Spot’s route will never take him within distance 0.001 of any tree.

-----Output-----
Write a single line containing the length needed for the leash in order for Spot to be able to get to all his toys, rounded to two decimal digits.

-----Examples-----
Sample Input:
2 0
10 0
10 10
Sample Output:
14.14

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One of the Hedgehog and his friend's favorite entertainments is to take some sentence or a song and replace half of the words (sometimes even all of them) with each other's names.

The friend's birthday is approaching and the Hedgehog decided to make a special present to his friend: a very long song, where his name will be repeated many times. But try as he might, he can't write a decent song!

The problem is that the Hedgehog has already decided how long the resulting sentence should be (i.e. how many letters it should contain) and in which positions in the sentence the friend's name should occur, and it must not occur in any other position in the sentence. Besides, the Hedgehog decided to limit himself to using only the first K letters of an English alphabet in this sentence (so it will be not even a sentence, but one long word).

The resulting problem is indeed quite complicated, that's why the Hedgehog asks you to help him and write a program that will make the desired word by the given name P, the length N of the required word, the given positions of the occurrences of the name P in the desired word and the alphabet's size K. Note that the occurrences of the name can overlap with each other.

Input

The first line contains numbers N and K which are the length of the required string and the alphabet size accordingly. The limitations are: 1 ≤ N ≤ 100, 2 ≤ K ≤ 26.

The second line contains the name P which is a non-empty string whose length does not exceed N characters. The string consists only of the first K lowercase symbols of an English alphabet.

The third line contains the string of length N - length(P) + 1, consisting only of numbers zero and one. A number one in the i-th position means that an occurrence of the name P should start from i-th position of the desired word, while a zero means that there is no occurrence starting here. 

Output

Print the desired word S. If there are several answers, print any of them.

If there is no solution, then print "No solution".

Examples

Input

5 2
aba
101


Output

ababa

Input

5 2
a
10001


Output

abbba

Input

6 2
abba
101


Output

No solution

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Malek is a rich man. He also is very generous. That's why he decided to split his money between poor people. A charity institute knows n poor people numbered from 1 to n. The institute gave Malek q recommendations. A recommendation is a segment of people like [l, r] which means the institute recommended that Malek gives one dollar to every person whose number is in this segment.

However this charity has very odd rules about the recommendations. Because of those rules the recommendations are given in such a way that for every two recommendation [a, b] and [c, d] one of the following conditions holds: 

  * The two segments are completely disjoint. More formally either a ≤ b < c ≤ d or c ≤ d < a ≤ b
  * One of the two segments are inside another. More formally either a ≤ c ≤ d ≤ b or c ≤ a ≤ b ≤ d. 



The goodness of a charity is the value of maximum money a person has after Malek finishes giving his money. The institute knows for each recommendation what is the probability that Malek will accept it. They want to know the expected value of goodness of this charity. So they asked you for help.

You have been given the list of recommendations and for each recommendation the probability of it being accepted by Malek. You have also been given how much money each person initially has. You must find the expected value of goodness.

Input

In the first line two space-separated integers n, q (1 ≤ n ≤ 105, 1 ≤ q ≤ 5000) are given.

In the second line n space-separated integers a1, a2, ..., an (0 ≤ ai ≤ 109) are given meaning that person number i initially has ai dollars. 

Each of the next q lines contains three space-separated numbers li, ri, pi (1 ≤ li ≤ ri ≤ n, 0 ≤ p ≤ 1) where li and ri are two integers describing the segment of recommendation and pi is a real number given with exactly three digits after decimal point which is equal to probability of Malek accepting this recommendation.

Note that a segment may appear several times in recommendations.

Output

Output the sought value. Your answer will be considered correct if its absolute or relative error is less than 10 - 6.

Examples

Input

5 2
1 7 2 4 3
1 3 0.500
2 2 0.500


Output

8.000000000


Input

5 2
281 280 279 278 282
1 4 1.000
1 4 0.000


Output

282.000000000


Input

3 5
1 2 3
1 3 0.500
2 2 0.250
1 2 0.800
1 1 0.120
2 2 0.900


Output

4.465000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Simon has a prime number x and an array of non-negative integers a_1, a_2, ..., a_{n}.

Simon loves fractions very much. Today he wrote out number $\frac{1}{x^{a} 1} + \frac{1}{x^{a_{2}}} + \ldots + \frac{1}{x^{a_{n}}}$ on a piece of paper. After Simon led all fractions to a common denominator and summed them up, he got a fraction: $\frac{s}{t}$, where number t equals x^{a}_1 + a_2 + ... + a_{n}. Now Simon wants to reduce the resulting fraction. 

Help him, find the greatest common divisor of numbers s and t. As GCD can be rather large, print it as a remainder after dividing it by number 1000000007 (10^9 + 7).


-----Input-----

The first line contains two positive integers n and x (1 ≤ n ≤ 10^5, 2 ≤ x ≤ 10^9) — the size of the array and the prime number.

The second line contains n space-separated integers a_1, a_2, ..., a_{n} (0 ≤ a_1 ≤ a_2 ≤ ... ≤ a_{n} ≤ 10^9). 


-----Output-----

Print a single number — the answer to the problem modulo 1000000007 (10^9 + 7).


-----Examples-----
Input
2 2
2 2

Output
8

Input
3 3
1 2 3

Output
27

Input
2 2
29 29

Output
73741817

Input
4 5
0 0 0 0

Output
1



-----Note-----

In the first sample $\frac{1}{4} + \frac{1}{4} = \frac{4 + 4}{16} = \frac{8}{16}$. Thus, the answer to the problem is 8.

In the second sample, $\frac{1}{3} + \frac{1}{9} + \frac{1}{27} = \frac{243 + 81 + 27}{729} = \frac{351}{729}$. The answer to the problem is 27, as 351 = 13·27, 729 = 27·27.

In the third sample the answer to the problem is 1073741824 mod 1000000007 = 73741817.

In the fourth sample $\frac{1}{1} + \frac{1}{1} + \frac{1}{1} + \frac{1}{1} = \frac{4}{1}$. Thus, the answer to the problem is 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ashish and Chandu were travelling to Japan. Chandu gave Ashish a weird lottery ticket which had a string S of length N containing lowercase Latin alphabets printed on it. The string corresponded to some number of points and Ashish wanted to maximize his points. All single characters from 'a' to 'z' and all pairs of characters 'aa','ab','ac', ... , 'zx','zy','zz' had value of 1 point. However, there were M special single characters and pairs which had a special value. These characters and pairs had a value greater than or equal to 1.

Ashish realized that in some cases, the string that he got could have more than one score. For example, if he got a string "aab", it could be interpreted in the following ways:
 1. a + a + b
 2. a + ab
 3. aa + b

Each of these ways would give Ashish some points. Help Ashish find out the maximum points that he can get.

Input
First line of input contains 2 integers N and M - the length of the string and the number of special values respectively.
Second line contains a string S of length N, containing lowercase Latin alphabets (a - z)
M lines follow. Each lines consists of 2 space-separated parts. Part 1 is either a single character or a pair of characters, and Part 2 is a positive integer. Part 2 is the special value of Part 1.

Output
Print a single integer - the maximum points scored by Ashish.

Constraints
1 ≤ N ≤ 100000
1 ≤ M ≤ 702
S contains lowercase Latin alphabets between 'a' to 'z' only.
1 ≤ Special value ≤ 100

SAMPLE INPUT
4 3
abcd
ab 10
bc 20
cd 30

SAMPLE OUTPUT
40

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The season for Snuke Festival has come again this year. First of all, Ringo will perform a ritual to summon Snuke. For the ritual, he needs an altar, which consists of three parts, one in each of the three categories: upper, middle and lower.
He has N parts for each of the three categories. The size of the i-th upper part is A_i, the size of the i-th middle part is B_i, and the size of the i-th lower part is C_i.
To build an altar, the size of the middle part must be strictly greater than that of the upper part, and the size of the lower part must be strictly greater than that of the middle part. On the other hand, any three parts that satisfy these conditions can be combined to form an altar.
How many different altars can Ringo build? Here, two altars are considered different when at least one of the three parts used is different.

-----Constraints-----
 - 1 \leq N \leq 10^5
 - 1 \leq A_i \leq 10^9(1\leq i\leq N)
 - 1 \leq B_i \leq 10^9(1\leq i\leq N)
 - 1 \leq C_i \leq 10^9(1\leq i\leq N)
 - All input values are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 ... A_N
B_1 ... B_N
C_1 ... C_N

-----Output-----
Print the number of different altars that Ringo can build.

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

-----Sample Output-----
3

The following three altars can be built:
 - Upper: 1-st part, Middle: 1-st part, Lower: 1-st part
 - Upper: 1-st part, Middle: 1-st part, Lower: 2-nd part
 - Upper: 1-st part, Middle: 2-nd part, Lower: 2-nd part

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
Given a number `n`, return a string representing it as a sum of distinct powers of three, or return `"Impossible"` if that's not possible to achieve.


# Input/Output


`[input]` integer `n`


A positive integer n. 

`1 ≤ n ≤ 10^16`.

`[output]` a string

A string representing the sum of powers of three which adds up to n, or `"Impossible"` if there is no solution. If the solution does exist, it should be return as `"3^a1+3^a2+ ... +3^an"`, where ai for `0 ≤ i ≤ n` represents the corresponding exponent of the term. The terms in the string should also be sorted in descending order, meaning that higher powers should appear before the lower ones in the string (`"3^0+3^1"` is incorrect, whereas `"3^1+3^0"` is correct).

# Example

For `n = 4`, the output should be `"3^1+3^0"`.

4 can be represented as `3+1` which is in fact 3 to the power of 1 plus 3 to the power of 0

For `n = 2`, the output should be `"Impossible"`.

There is no way to represent 2 as a sum of `distinct powers` of 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a binary matrix $A$ of size $n \times n$. Let's denote an $x$-compression of the given matrix as a matrix $B$ of size $\frac{n}{x} \times \frac{n}{x}$ such that for every $i \in [1, n], j \in [1, n]$ the condition $A[i][j] = B[\lceil \frac{i}{x} \rceil][\lceil \frac{j}{x} \rceil]$ is met.

Obviously, $x$-compression is possible only if $x$ divides $n$, but this condition is not enough. For example, the following matrix of size $2 \times 2$ does not have any $2$-compression:

 $01$   $10$ 

For the given matrix $A$, find maximum $x$ such that an $x$-compression of this matrix is possible.

Note that the input is given in compressed form. But even though it is compressed, you'd better use fast input.


-----Input-----

The first line contains one number $n$ ($4 \le n \le 5200$) — the number of rows and columns in the matrix $A$. It is guaranteed that $n$ is divisible by $4$.

Then the representation of matrix follows. Each of $n$ next lines contains $\frac{n}{4}$ one-digit hexadecimal numbers (that is, these numbers can be represented either as digits from $0$ to $9$ or as uppercase Latin letters from $A$ to $F$). Binary representation of each of these numbers denotes next $4$ elements of the matrix in the corresponding row. For example, if the number $B$ is given, then the corresponding elements are 1011, and if the number is $5$, then the corresponding elements are 0101.

Elements are not separated by whitespaces.


-----Output-----

Print one number: maximum $x$ such that an $x$-compression of the given matrix is possible.


-----Examples-----
Input
8
E7
E7
E7
00
00
E7
E7
E7

Output
1

Input
4
7
F
F
F

Output
1



-----Note-----

The first example corresponds to the matrix:  $11100111$   $11100111$   $11100111$   $00000000$   $00000000$   $11100111$   $11100111$   $11100111$ 

It is easy to see that the answer on this example is $1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given is a permutation P_1, \ldots, P_N of 1, \ldots, N.
Find the number of integers i (1 \leq i \leq N) that satisfy the following condition:  
 - For any integer j (1 \leq j \leq i), P_i \leq P_j.

-----Constraints-----
 - 1 \leq N \leq 2 \times 10^5
 - P_1, \ldots, P_N is a permutation of 1, \ldots, N.  
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
P_1 ... P_N

-----Output-----
Print the number of integers i that satisfy the condition.

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

-----Sample Output-----
3

i=1, 2, and 4 satisfy the condition, but i=3 does not - for example, P_i > P_j holds for j = 1.

Similarly, i=5 does not satisfy the condition, either. Thus, there are three integers that satisfy the condition.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One department of some software company has $n$ servers of different specifications. Servers are indexed with consecutive integers from $1$ to $n$. Suppose that the specifications of the $j$-th server may be expressed with a single integer number $c_j$ of artificial resource units.

In order for production to work, it is needed to deploy two services $S_1$ and $S_2$ to process incoming requests using the servers of the department. Processing of incoming requests of service $S_i$ takes $x_i$ resource units.

The described situation happens in an advanced company, that is why each service may be deployed using not only one server, but several servers simultaneously. If service $S_i$ is deployed using $k_i$ servers, then the load is divided equally between these servers and each server requires only $x_i / k_i$ (that may be a fractional number) resource units.

Each server may be left unused at all, or be used for deploying exactly one of the services (but not for two of them simultaneously). The service should not use more resources than the server provides.

Determine if it is possible to deploy both services using the given servers, and if yes, determine which servers should be used for deploying each of the services.

Input Specification:
The first line contains three integers $n$, $x_1$, $x_2$ ($2 \leq n \leq 300\,000$, $1 \leq x_1, x_2 \leq 10^9$) — the number of servers that the department may use, and resource units requirements for each of the services.

The second line contains $n$ space-separated integers $c_1, c_2, \ldots, c_n$ ($1 \leq c_i \leq 10^9$) — the number of resource units provided by each of the servers.

Output Specification:
If it is impossible to deploy both services using the given servers, print the only word "No" (without the quotes).

Otherwise print the word "Yes" (without the quotes). 

In the second line print two integers $k_1$ and $k_2$ ($1 \leq k_1, k_2 \leq n$) — the number of servers used for each of the services.

In the third line print $k_1$ integers, the indices of the servers that will be used for the first service.

In the fourth line print $k_2$ integers, the indices of the servers that will be used for the second service.

No index may appear twice among the indices you print in the last two lines. If there are several possible answers, it is allowed to print any of them.

Demo Input:
['6 8 16\n3 5 2 9 8 7\n', '4 20 32\n21 11 11 12\n', '4 11 32\n5 5 16 16\n', '5 12 20\n7 8 4 11 9\n']

Demo Output:
['Yes\n3 2\n1 2 6\n5 4', 'Yes\n1 3\n1\n2 3 4\n', 'No\n', 'No\n']

Note:
In the first sample test each of the servers 1, 2 and 6 will will provide $8 / 3 = 2.(6)$ resource units and each of the servers 5, 4 will provide $16 / 2 = 8$ resource units.

In the second sample test the first server will provide $20$ resource units and each of the remaining servers will provide $32 / 3 = 10.(6)$ resource units.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lenny is playing a game on a 3 × 3 grid of lights. In the beginning of the game all lights are switched on. Pressing any of the lights will toggle it and all side-adjacent lights. The goal of the game is to switch all the lights off. We consider the toggling as follows: if the light was switched on then it will be switched off, if it was switched off then it will be switched on.

Lenny has spent some time playing with the grid and by now he has pressed each light a certain number of times. Given the number of times each light is pressed, you have to print the current state of each light.


-----Input-----

The input consists of three rows. Each row contains three integers each between 0 to 100 inclusive. The j-th number in the i-th row is the number of times the j-th light of the i-th row of the grid is pressed.


-----Output-----

Print three lines, each containing three characters. The j-th character of the i-th line is "1" if and only if the corresponding light is switched on, otherwise it's "0".


-----Examples-----
Input
1 0 0
0 0 0
0 0 1

Output
001
010
100

Input
1 0 1
8 8 8
2 0 3

Output
010
011
100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rhezo likes to play with graphs having N nodes and M edges. Lonewolf is ready to give him such a graph only on one condition. He wants Rhezo to find the number of critical links in the graph. 

A critical link in a graph is an edge that has the following property: If we cut the link/edge, the graph will have exactly one more connected component than it previously had, and the difference between the number of nodes on each side of the edge is less than a certain integer P. 

Given P and the graph, can you help Rhezo calculate the number of critical links?

Input:

First line contains 3 integers N, M and P as described in the problem statement. Each of the next M lines contain 2 integers A and B, meaning that node number A has a link/edge with node number B.

Output:

Find the number of critical links in the graph.

Constraints:

1 ≤ N, M, P ≤ 10^{5} 

1 ≤ A,B ≤ N

1 ≤ M ≤ max(10^{5},N \cdot (N-1) / 2)

SAMPLE INPUT
5 4 100
1 2
2 3
3 4
4 5

SAMPLE OUTPUT
4

Explanation

Each edge is a critical link.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e The length of the garden is n).
There are n + 1 taps located at points [0, 1, ..., n] in the garden.
Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open.
Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.
 
Example 1:

Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: The tap at point 0 can cover the interval [-3,3]
The tap at point 1 can cover the interval [-3,5]
The tap at point 2 can cover the interval [1,3]
The tap at point 3 can cover the interval [2,4]
The tap at point 4 can cover the interval [4,4]
The tap at point 5 can cover the interval [5,5]
Opening Only the second tap will water the whole garden [0,5]

Example 2:
Input: n = 3, ranges = [0,0,0,0]
Output: -1
Explanation: Even if you activate all the four taps you cannot water the whole garden.

Example 3:
Input: n = 7, ranges = [1,2,1,0,2,1,0,1]
Output: 3

Example 4:
Input: n = 8, ranges = [4,0,0,0,0,0,0,0,4]
Output: 2

Example 5:
Input: n = 8, ranges = [4,0,0,0,4,0,0,0,4]
Output: 1

 
Constraints:

1 <= n <= 10^4
ranges.length == n + 1
0 <= ranges[i] <= 100

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