vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Snuke got a grid from his mother, as a birthday present. The grid has H rows and W columns. Each cell is painted black or white. All black cells are 4-connected, that is, it is possible to traverse from any black cell to any other black cell by just visiting black cells, where it is only allowed to move horizontally or vertically.

The color of the cell at the i-th row and j-th column (1 ≦ i ≦ H, 1 ≦ j ≦ W) is represented by a character s_{ij}. If s_{ij} is `#`, the cell is painted black. If s_{ij} is `.`, the cell is painted white. At least one cell is painted black.

We will define fractals as follows. The fractal of level 0 is a 1 × 1 grid with a black cell. The fractal of level k+1 is obtained by arranging smaller grids in H rows and W columns, following the pattern of the Snuke's grid. At a position that corresponds to a black cell in the Snuke's grid, a copy of the fractal of level k is placed. At a position that corresponds to a white cell in the Snuke's grid, a grid whose cells are all white, with the same dimensions as the fractal of level k, is placed.

You are given the description of the Snuke's grid, and an integer K. Find the number of connected components of black cells in the fractal of level K, modulo 10^9+7.

Constraints

* 1 ≦ H,W ≦ 1000
* 0 ≦ K ≦ 10^{18}
* Each s_{ij} is either `#` or `.`.
* All black cells in the given grid are 4-connected.
* There is at least one black cell in the given grid.

Input

The input is given from Standard Input in the following format:


H W K
s_{11} .. s_{1W}
:
s_{H1} .. s_{HW}


Output

Print the number of connected components of black cells in the fractal of level K, modulo 10^9+7.

Examples

Input

3 3 3
.#.
###
#.#


Output

20


Input

3 3 3
.#.

.#


Output

20


Input

3 3 3

.#


Output

1


Input

11 15 1000000000000000000
.....#.........
....###........
....####.......
...######......
...#######.....
..##.###.##....
..##########...
.###.....####..
.####...######.

.##..##..##..#


Output

301811921

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is a big fan of soccer! He loves soccer so much that he even invented soccer for dogs! Here are the rules of soccer for dogs:
- N$N$ dogs (numbered 1$1$ through N$N$) stand in a line in such a way that for each valid i$i$, dogs i$i$ and i+1$i + 1$ are adjacent.
- Each dog has a skill level, which is either 1$1$ or 2$2$.
- At the beginning of the game, Chef passes a ball to dog 1$1$ (dog 1$1$ receives the ball).
- For each valid i$i$, if dog i$i$ has skill level s$s$, this dog can pass the ball to any dog with number j$j$ such that 1≤|i−j|≤s$1 \le |i-j| \le s$.
- Each dog (including dog 1$1$) may receive the ball at most once.
- Whenever a dog receives the ball, it must either pass it to another dog or finish the game by scoring a goal.
While the dogs were playing, Chef also created a game for developers. He defined the result of a game of soccer for dogs as the sequence of dogs which received the ball in the order in which they received it. The last dog in the sequence is the dog that decided to score a goal; if a dog never received the ball, it does not appear in the sequence. In the game for developers, you should find the number of possible results of soccer for dogs.
Find this number of possible results modulo 109+7$10^9 + 7$. Two results of soccer for dogs (sequences of dogs' numbers) are considered different if these sequences have different lengths or if there is a valid index i$i$ such that the i$i$-th dog in one sequence is different from the i$i$-th dog in the other sequence.

-----Input-----
- The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
- The first line of each test case contains a single integer N$N$.
- The second line contains N$N$ space-separated integers A1,A2,…,AN$A_1, A_2, \ldots, A_N$ denoting the skill levels of the dogs.

-----Output-----
For each test case, print a single line containing one integer - the number of different results of soccer for dogs, modulo 109+7$10^9 + 7$.

-----Constraints-----
- 1≤T≤10$1 \le T \le 10$
- 1≤N≤105$1 \le N \le 10^5$
- 1≤Ai≤2$1 \le A_i \le 2$ for each valid i$i$

-----Subtasks-----
Subtask #1 (10 points): N≤10$N \le 10$
Subtask #2 (30 points): N≤103$N \le 10^3$
Subtask #3 (60 points): original constraints

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

-----Example Output-----
4
5
6

-----Explanation-----
Example case 1: The following results are possible: 1$1$, [1,2]$[1, 2]$, [1,2,3]$[1, 2, 3]$, [1,2,3,4]$[1, 2, 3, 4]$.
Example case 2: The following results are possible: [1]$[1]$, [1,2]$[1, 2]$, [1,2,3]$[1, 2, 3]$, [1,3,2]$[1, 3, 2]$, [1,3]$[1, 3]$.

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

Limak is a brown bear.
Brown bears often climb trees and so does Limak.
As you probably know, bears use ropes to move between tops of trees.

There are N trees in a row.
i-th of them grows at coordinate X[i] and has height H[i].
A further tree is always higher - it's guaranteed that X[i] < X[i+1] and H[i] < H[i+1].

Limak is currently at the top of the first tree and he has a rope of length L.
He wants to be at the top of the last tree.
He can move from a-th to b-th tree if and only if all tree conditions are fulfilled:
1) a < b
2) (X[b]-X[a])^2 + (H[b]-H[a])^2 ≤ L - rope must be long enough
3) H[b]-H[a] < X[b]-X[a] - it's not safe to go very uphill

Note that there is no square root in the second condition.
The reason is that bears calculate distances a bit different than people.

Limak doesn't know if his rope is long enough.
Could you help him and calculate the minimum L for which he can get from the first tree to the last one?
Print -1 instead if there is no L for which Limak would reach the last tree.

Input format:

The first line contains one integer number N, denoting number of trees.
i-th of the next N lines contains two integer numbers X[i] and H[i], describing i-th tree.

Output format:

In the single line print the minimum possible L for which Limak would be able to get from the first to the last tree.
If there is no such L, print -1 instead.

Constraints:

2 ≤ N ≤ 10^6
1 ≤ X[i], H[i] ≤ 10^7
X[i] < X[i+1]
H[i] < H[i+1]

SAMPLE INPUT
4
3 2
4 3
13 4
15 5

SAMPLE OUTPUT
104

Explanation

Limak can't go to the second tree because inequality H[2]-H[1] < X[2]-X[1] doesn't hold.
With rope of length at least 10^2 + 2^2 = 104 he can go from the first to the third tree.
Then he needs rope of length at least 2^2 + 1^2 = 5 to get to the last tree.
So he can reach the last tree with L = 104.

Limak can also skip a third tree and go directly to the last one but he would need L = 12^2+3^2 = 153.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given are three integers A_1, A_2, and A_3.
If A_1+A_2+A_3 is greater than or equal to 22, print bust; otherwise, print win.

-----Constraints-----
 - 1 \leq A_i \leq 13 \ \ (i=1,2,3)
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
A_1 A_2 A_3

-----Output-----
If A_1+A_2+A_3 is greater than or equal to 22, print bust; otherwise, print win.

-----Sample Input-----
5 7 9

-----Sample Output-----
win

5+7+9=21, so print win.

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

Time Limit: 1 seconds

Memory Limit: 64 megabytes

Problem Description:
Once Bob took a paper stripe of n squares (the height of the stripe is 1 square). In each square he wrote an integer number, possibly negative. He became interested in how many ways exist to cut this stripe into three pieces so that the sum of numbers from each piece is equal to the sum of numbers from any other piece, and each piece contains positive integer amount of squares. Would you help Bob solve this problem?

Input Specification:
The first input line contains integer *n* (1<=≤<=*n*<=≤<=105) — amount of squares in the stripe. The second line contains n space-separated numbers — they are the numbers written in the squares of the stripe. These numbers are integer and do not exceed 10000 in absolute value.

Output Specification:
Output the amount of ways to cut the stripe into three non-empty pieces so that the sum of numbers from each piece is equal to the sum of numbers from any other piece. Don't forget that it's allowed to cut the stripe along the squares' borders only.

Demo Input:
['4\n1 2 3 3\n', '5\n1 2 3 4 5\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer a that consists of n digits. You are also given a sequence of digits s of length m. The digit in position j (1 ≤ j ≤ m) of sequence s means that you can choose an arbitrary position i (1 ≤ i ≤ n) in a and replace the digit in the chosen position i with sj. Each element in the sequence s can participate in no more than one replacing operation.

Your task is to perform such sequence of replacements, that the given number a gets maximum value. You are allowed to use not all elements from s.

Input

The first line contains positive integer a. Its length n is positive and doesn't exceed 105. The second line contains sequence of digits s. Its length m is positive and doesn't exceed 105. The digits in the sequence s are written consecutively without any separators.

The given number a doesn't contain leading zeroes. 

Output

Print the maximum value that can be obtained from a after a series of replacements. You are allowed to use not all elements from s. The printed number shouldn't contain any leading zeroes.

Examples

Input

1024
010


Output

1124


Input

987
1234567


Output

987

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N mountains ranging from east to west, and an ocean to the west.
At the top of each mountain, there is an inn. You have decided to choose where to stay from these inns.
The height of the i-th mountain from the west is H_i.
You can certainly see the ocean from the inn at the top of the westmost mountain.
For the inn at the top of the i-th mountain from the west (i = 2, 3, ..., N), you can see the ocean if and only if H_1 \leq H_i, H_2 \leq H_i, ..., and H_{i-1} \leq H_i.
From how many of these N inns can you see the ocean?

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 20
 - 1 \leq H_i \leq 100

-----Input-----
Input is given from Standard Input in the following format:
N
H_1 H_2 ... H_N

-----Output-----
Print the number of inns from which you can see the ocean.

-----Sample Input-----
4
6 5 6 8

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

You can see the ocean from the first, third and fourth inns from the west.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array arr[] of N integers which may contain duplicate elements, the index of an element of this array is given to us, the task is to find the final position of this element ( for which the index is given) in the array after the stable sort is applied on the array. 
 
Example 1:
Input: N = 10, INDEX = 5
arr[]= {3, 4, 3, 5, 2, 3, 4, 3, 1, 5}
Output: 4
Explanation: Element initial index – 5 
(third 3) After sorting array by stable 
sorting algorithm,we get array as shown 
below [1(8), 2(4), 3(0), 3(2), 3(5), 3(7),
4(1), 4(6), 5(3), 5(9)] with their 
initial indices shown in parentheses next 
to them,Element's index after sorting = 4.
 
Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function getIndexInSortedArray() that takes array arr, integer N, and integer index as parameters and returns the number of uneaten leaves.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{6}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Rebel fleet is on the run. It consists of m ships currently gathered around a single planet. Just a few seconds ago, the vastly more powerful Empire fleet has appeared in the same solar system, and the Rebels will need to escape into hyperspace. In order to spread the fleet, the captain of each ship has independently come up with the coordinate to which that ship will jump. In the obsolete navigation system used by the Rebels, this coordinate is given as the value of an arithmetic expression of the form $\frac{a + b}{c}$.

To plan the future of the resistance movement, Princess Heidi needs to know, for each ship, how many ships are going to end up at the same coordinate after the jump. You are her only hope!


-----Input-----

The first line of the input contains a single integer m (1 ≤ m ≤ 200 000) – the number of ships. The next m lines describe one jump coordinate each, given as an arithmetic expression. An expression has the form (a+b)/c. Namely, it consists of: an opening parenthesis (, a positive integer a of up to two decimal digits, a plus sign +, a positive integer b of up to two decimal digits, a closing parenthesis ), a slash /, and a positive integer c of up to two decimal digits.


-----Output-----

Print a single line consisting of m space-separated integers. The i-th integer should be equal to the number of ships whose coordinate is equal to that of the i-th ship (including the i-th ship itself).


-----Example-----
Input
4
(99+98)/97
(26+4)/10
(12+33)/15
(5+1)/7

Output
1 2 2 1 


-----Note-----

In the sample testcase, the second and the third ship will both end up at the coordinate 3.

Note that this problem has only two versions – easy and hard.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a string $s$ of length $3$, consisting of uppercase and lowercase English letters. Check if it is equal to "YES" (without quotes), where each letter can be in any case. For example, "yES", "Yes", "yes" are all allowable.


-----Input-----

The first line of the input contains an integer $t$ ($1 \leq t \leq 10^3$) — the number of testcases.

The description of each test consists of one line containing one string $s$ consisting of three characters. Each character of $s$ is either an uppercase or lowercase English letter.


-----Output-----

For each test case, output "YES" (without quotes) if $s$ satisfies the condition, and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).


-----Examples-----

Input
10
YES
yES
yes
Yes
YeS
Noo
orZ
yEz
Yas
XES
Output
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO


-----Note-----

The first five test cases contain the strings "YES", "yES", "yes", "Yes", "YeS". All of these are equal to "YES", where each character is either uppercase or lowercase.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given the string S . Compress the string when lower and upper cases are the same. In compressed string characters should be in lowercase.
Example 1:
Input: S = "aaABBb"
Output: "3a3b"
Explanation: As 'a' appears 3 times
consecutively and 'b' also 3 times,
and 'b' and 'B' considered as same. 
Ã¢â¬â¹Example 2:
Input: S = "aaacca"
Output: "3a2c1a"
Explanation: As 'a' appears 3 times
consecutively and 'c' also 2 times,
and then 'a' 1 time.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function transform() which takes the string S as inputs and returns the compressed string.
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ |S| ≤ 2 * 10^{5}
S contains only lowercase and uppercase characters.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a bingo card with a 3\times3 grid. The square at the i-th row from the top and the j-th column from the left contains the number A_{i, j}.
The MC will choose N numbers, b_1, b_2, \cdots, b_N. If our bingo sheet contains some of those numbers, we will mark them on our sheet.
Determine whether we will have a bingo when the N numbers are chosen, that is, the sheet will contain three marked numbers in a row, column, or diagonal.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq A_{i, j} \leq 100
 - A_{i_1, j_1} \neq A_{i_2, j_2} ((i_1, j_1) \neq (i_2, j_2))
 - 1 \leq N \leq 10
 - 1 \leq b_i \leq 100
 - b_i \neq b_j (i \neq j)

-----Input-----
Input is given from Standard Input in the following format:
A_{1, 1} A_{1, 2} A_{1, 3}
A_{2, 1} A_{2, 2} A_{2, 3}
A_{3, 1} A_{3, 2} A_{3, 3}
N
b_1
\vdots
b_N

-----Output-----
If we will have a bingo, print Yes; otherwise, print No.

-----Sample Input-----
84 97 66
79 89 11
61 59 7
7
89
7
87
79
24
84
30

-----Sample Output-----
Yes

We will mark A_{1, 1}, A_{2, 1}, A_{2, 2}, A_{3, 3}, and complete the diagonal from the top-left to the bottom-right.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N points on X-Y plane with integer coordinates (xi, yi). You are given a set of polygons with all of its edges parallel to the axes (in other words, all angles of the polygons are 90 degree angles and all lines are in the cardinal directions. There are no diagonals). For each polygon your program should find the number of points lying inside it. A point located on the border of polygon is also considered to be inside the polygon.

Input Format 

The first line contains two integers N and Q. The next line contains N space-separated integer coordinates (xi,yi). Q queries follow. Each query consists of a single integer Mi in the first line, followed by Mi space separated integer coordinates (x[i][j],y[i][j]) specifying the boundary of the query polygon in clock-wise order.

Polygon is an alternating sequence of vertical line segments and horizontal line segments.
Polygon has Mi edges, where (x[i][j],y[i][j]) is connected to (x[i][(j+1)%Mi], y[i][(j+1)%Mi].
For each 0 <= j < Mi, either x[i][(j+1)%Mi] == x[i][j] or y[i][(j+1)%Mi] == y[i][j] but not both.
It is guaranteed that the polygon is not self-intersecting.

Output Format 

For each query output the number of points inside the query polygon in a separate line.

Constraints 

1 <= N <= 20,000 

1 <= Q <= 20,000 

4 <= Mi <= 20 

-200,000 <= x[i][j],y[i][j] <= 200,000

Sample Input #1 

16 2 

0 0 

0 1 

0 2 

0 3 

1 0 

1 1 

1 2 

1 3 

2 0 

2 1 

2 2 

2 3 

3 0 

3 1 

3 2 

3 3 

8 

0 0 

0 1 

1 1 

1 2 

0 2 

0 3 

3 3 

3 0 

4 

0 0 

0 1 

1 1 

1 0

Sample Output #1: 

16 

4

Sample Input #2: 

6 1 

1 1 

3 3 

3 5 

5 2 

6 3 

7 4 

10 

1 3 

1 6 

4 6 

4 3 

6 3 

6 1 

4 1 

4 2 

3 2 

3 3

Sample Output #2: 

4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 Your task is to find the similarity of given sorted arrays `a` and `b`, which is defined as follows: 
 
 you take the number of elements which are present in both arrays and divide it by the number of elements which are present in at least one array.

 It also can be written as a formula `similarity(A, B) = #(A ∩ B) / #(A ∪ B)`, where `#(C)` is the number of elements in C, `∩` is intersection of arrays, `∪` is union of arrays.

 This is known as `Jaccard similarity`.

 The result is guaranteed to fit any floating-point type without rounding.

# Example

 For `a = [1, 2, 4, 6, 7]` and `b = [2, 3, 4, 7]`:
```
elements [2, 4, 7] are present in both arrays;
elements [1, 2, 3, 4, 6, 7] are present in at least one of the arrays.
So the similarity equals to 3 / 6 = 0.5.```

# Input/Output


 - `[input]` integer array `a`

  A `sorted` array of positive integers. 
  
  All elements are `different` and are `less than 100`.
  
  `1 ≤ a.length ≤ 100`


 - `[input]` integer array `b`

  An array in the same format as `a`.


 - `[output]` a float number

  The similarity of the arrays.
  
  ```Haskell
  
  In Haskell the two arrays are passed as a touple.
  ```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are a newly designed and created robot. As a robot, you are excellent at shooting lasers: your lasers always go perfectly straight, go infinitely far, and are infinitely thin. To test you, the scientist who made you set out a number of targets for you to hit with your laser beam. The targets (point-like objects) are set up in a large, open room.

Unfortunately, you are running low on battery. You only have enough charge left to fire two shots. The targets are transparent, so you might be able to shoot multiple targets with your laser beam. In fact, you are able to hit an infinite number of targets with a single shot, as long as they are on a straight line. In addition, you can move anywhere before and between the two shots. Can you figure out if it is possible to hit all targets with at most two shots from your laser beams?

-----Input-----
The first line contains an integer $N$, satisfying $1 \leq N \leq 100000$, the number of targets.

The following $N$ lines each contain two integers $X_ i$ and $Y_ i$, satisfying $-10^9 \leq X_ i,Y_ i \leq 10^9$. Each pair $(X_ i,Y_ i)$ specifies the coordinates of one of the $N$ targets. No two targets are placed at the same coordinates.

You may assume that height does not play a role in this problem.

-----Output-----
Output a single line containing a single word: “success” if it is possible to line up the two shots so that they hit all the targets, and “failure” if it is not.

-----Examples-----
Sample Input:
6
-1 0
0 0
1 0
-1 1
0 2
1 1
Sample Output:
failure

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Being a programmer, you like arrays a lot. For your birthday, your friends have given you an array *a* consisting of *n* distinct integers.

Unfortunately, the size of *a* is too small. You want a bigger array! Your friends agree to give you a bigger array, but only if you are able to answer the following question correctly: is it possible to sort the array *a* (in increasing order) by reversing exactly one segment of *a*? See definitions of segment and reversing in the notes.

Input Specification:
The first line of the input contains an integer *n* (1<=≤<=*n*<=≤<=105) — the size of array *a*.

The second line contains *n* distinct space-separated integers: *a*[1],<=*a*[2],<=...,<=*a*[*n*] (1<=≤<=*a*[*i*]<=≤<=109).

Output Specification:
Print "yes" or "no" (without quotes), depending on the answer.

If your answer is "yes", then also print two space-separated integers denoting start and end (start must not be greater than end) indices of the segment to be reversed. If there are multiple ways of selecting these indices, print any of them.

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

Demo Output:
['yes\n1 3\n', 'yes\n1 2\n', 'no\n', 'yes\n1 1\n']

Note:
Sample 1. You can reverse the entire array to get [1, 2, 3], which is sorted.

Sample 3. No segment can be reversed such that the array will be sorted.

Definitions

A segment [*l*, *r*] of array *a* is the sequence *a*[*l*], *a*[*l* + 1], ..., *a*[*r*].

If you have an array *a* of size *n* and you reverse its segment [*l*, *r*], the array will become:

*a*[1], *a*[2], ..., *a*[*l* - 2], *a*[*l* - 1], *a*[*r*], *a*[*r* - 1], ..., *a*[*l* + 1], *a*[*l*], *a*[*r* + 1], *a*[*r* + 2], ..., *a*[*n* - 1], *a*[*n*].

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