vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A $10\times10$ Crossword grid is provided to you, along with a set of words (or names of places) which need to be filled into the grid.  Cells are marked either + or -.  Cells marked with a - are to be filled with the word list.  

The following shows an example crossword from the input $crossword$ grid and the list of words to fit, $words=[PLAND,LHASA,SPAIN,INDIA]$:

Input 	   		Output

++++++++++ 		++++++++++
+------+++ 		+POLAND+++
+++-++++++ 		+++H++++++
+++-++++++ 		+++A++++++
+++-----++ 		+++SPAIN++
+++-++-+++ 		+++A++N+++
++++++-+++ 		++++++D+++
++++++-+++ 		++++++I+++
++++++-+++ 		++++++A+++
++++++++++ 		++++++++++
POLAND;LHASA;SPAIN;INDIA

Function Description

Complete the crosswordPuzzle function in the editor below.  It should return an array of strings, each representing a row of the finished puzzle.

crosswordPuzzle has the following parameter(s):  

crossword: an array of $10$ strings of length $10$ representing the empty grid  
words: a string consisting of semicolon delimited strings to fit into $crossword$  

Input Format

Each of the first $10$ lines represents $crossword[i]$, each of which has $10$ characters, $crossword[i][j]$.

The last line contains a string consisting of semicolon delimited $words[i]$ to fit.  

Constraints

$1\leq|words|\leq10$ 

$crossword[i][j]\in\{+,-\}$ 

$words[i][j]\in ascii[A-Z]$  

Output Format

Position the words appropriately in the $10\times10$ grid, then return your array of strings for printing.  

Sample Input 0
+-++++++++
+-++++++++
+-++++++++
+-----++++
+-+++-++++
+-+++-++++
+++++-++++
++------++
+++++-++++
+++++-++++
LONDON;DELHI;ICELAND;ANKARA

Sample Output 0
+L++++++++
+O++++++++
+N++++++++
+DELHI++++
+O+++C++++
+N+++E++++
+++++L++++
++ANKARA++
+++++N++++
+++++D++++

Sample Input 1
+-++++++++
+-++++++++
+-------++
+-++++++++
+-++++++++
+------+++
+-+++-++++
+++++-++++
+++++-++++
++++++++++
AGRA;NORWAY;ENGLAND;GWALIOR

Sample Output 1
+E++++++++
+N++++++++
+GWALIOR++
+L++++++++
+A++++++++
+NORWAY+++
+D+++G++++
+++++R++++
+++++A++++
++++++++++

Sample Input 2
++++++-+++
++------++
++++++-+++
++++++-+++
+++------+
++++++-+-+
++++++-+-+
++++++++-+
++++++++-+
++++++++-+
ICELAND;MEXICO;PANAMA;ALMATY

Sample Output 2
++++++I+++
++MEXICO++
++++++E+++
++++++L+++
+++PANAMA+
++++++N+L+
++++++D+M+
++++++++A+
++++++++T+
++++++++Y+

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

— Welcome home, Chtholly.

— I kept my promise...

— I made it... I really made it!

After several days of fighting, Chtholly Nota Seniorious miraculously returned from the fierce battle.

As promised, Willem is now baking butter cake for her.

However, although Willem is skilled in making dessert, he rarely bakes butter cake.

This time, Willem made a big mistake — he accidentally broke the oven!

Fortunately, Chtholly decided to help him.

Willem puts n cakes on a roll, cakes are numbered from 1 to n, the i-th cake needs ai seconds of baking.

Willem needs Chtholly to do m operations to bake the cakes.

Operation 1: 1 l r x

Willem asks Chtholly to check each cake in the range [l, r], if the cake needs to be baked for more than x seconds, he would bake it for x seconds and put it back in its place. More precisely, for every i in range [l, r], if ai is strictly more than x, ai becomes equal ai - x.

Operation 2: 2 l r x

Willem asks Chtholly to count the number of cakes in the range [l, r] that needs to be cooked for exactly x seconds. More formally you should find number of such i in range [l, r], that ai = x.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 105).

The second line contains n integers, i-th of them is ai (1 ≤ ai ≤ 105).

The next m lines are the m operations described above. It is guaranteed that 1 ≤ l ≤ r ≤ n and 1 ≤ x ≤ 105.

Output

For each operation of the second type, print the answer.

Examples

Input

5 6
1 5 5 5 8
2 2 5 5
1 2 4 3
2 2 5 2
2 2 5 5
1 3 5 1
2 1 5 1


Output

3
3
0
3


Input

7 7
1 9 2 6 8 1 7
2 1 7 1
2 2 5 2
1 4 7 7
2 2 4 2
1 3 4 5
2 3 3 3
2 3 7 2


Output

2
1
1
0
1


Input

8 13
75 85 88 100 105 120 122 128
1 1 8 70
2 3 8 30
1 3 8 3
2 2 5 15
1 2 4 10
2 1 5 5
1 2 7 27
2 1 5 5
1 3 7 12
1 1 7 4
2 1 8 1
1 4 8 5
2 1 8 1


Output

1
2
3
4
5
6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Anders talks in the Swedish dialect of östgötska. Unfortunately, this makes it somewhat hard to get a programming job in the Swedish capital of Stockholm. The trendy Stockholm hipsters only accept applicants speaking the standard Swedish dialect, rikssvenska.

To increase his chances of passing interviews, he wishes to practice talking rikssvenska. To help him with this, he wants you to write a program that can determine whenever he accidentally reverts to speaking östgötska.

A simple way of determining if a sentence is written in östgötska is if at least $40\% $ of the words in the sentence contains the letter ä. For simplicity, this is encoded as the letter combination ae (meaning any appearance of the substring ae is to be regarded as an occurrence of the letter ä).

-----Input-----
The first and only line of input contains a sequence of space-separated words. Each word consists only of letters a-z. There are at most $100$ words, and each word contains at most $15$ letters a-z (meaning that the ae combination counts as two letters for this limit).

-----Output-----
Output “dae ae ju traeligt va” if the input sentence is in östgötska, otherwise output “haer talar vi rikssvenska”.

-----Examples-----
Sample Input:
dae ae ju traeligt va
Sample Output:
dae ae ju traeligt va

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
They say "years are like dominoes, tumbling one after the other". But would a year fit into a grid? I don't think so.

Limak is a little polar bear who loves to play. He has recently got a rectangular grid with h rows and w columns. Each cell is a square, either empty (denoted by '.') or forbidden (denoted by '#'). Rows are numbered 1 through h from top to bottom. Columns are numbered 1 through w from left to right.

Also, Limak has a single domino. He wants to put it somewhere in a grid. A domino will occupy exactly two adjacent cells, located either in one row or in one column. Both adjacent cells must be empty and must be inside a grid.

Limak needs more fun and thus he is going to consider some queries. In each query he chooses some rectangle and wonders, how many way are there to put a single domino inside of the chosen rectangle?


-----Input-----

The first line of the input contains two integers h and w (1 ≤ h, w ≤ 500) – the number of rows and the number of columns, respectively.

The next h lines describe a grid. Each line contains a string of the length w. Each character is either '.' or '#' — denoting an empty or forbidden cell, respectively.

The next line contains a single integer q (1 ≤ q ≤ 100 000) — the number of queries.

Each of the next q lines contains four integers r1_{i}, c1_{i}, r2_{i}, c2_{i} (1 ≤ r1_{i} ≤ r2_{i} ≤ h, 1 ≤ c1_{i} ≤ c2_{i} ≤ w) — the i-th query. Numbers r1_{i} and c1_{i} denote the row and the column (respectively) of the upper left cell of the rectangle. Numbers r2_{i} and c2_{i} denote the row and the column (respectively) of the bottom right cell of the rectangle.


-----Output-----

Print q integers, i-th should be equal to the number of ways to put a single domino inside the i-th rectangle.


-----Examples-----
Input
5 8
....#..#
.#......
##.#....
##..#.##
........
4
1 1 2 3
4 1 4 1
1 2 4 5
2 5 5 8

Output
4
0
10
15

Input
7 39
.......................................
.###..###..#..###.....###..###..#..###.
...#..#.#..#..#.........#..#.#..#..#...
.###..#.#..#..###.....###..#.#..#..###.
.#....#.#..#....#.....#....#.#..#..#.#.
.###..###..#..###.....###..###..#..###.
.......................................
6
1 1 3 20
2 10 6 30
2 10 7 30
2 2 7 7
1 7 7 7
1 8 7 8

Output
53
89
120
23
0
2



-----Note-----

A red frame below corresponds to the first query of the first sample. A domino can be placed in 4 possible ways. [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this Kata, you will be given a string with brackets and an index of an opening bracket and your task will be to return the index of the matching closing bracket.  Both the input and returned index are 0-based **except in Fortran where it is 1-based**. An opening brace will always have a closing brace. Return `-1` if there is no answer (in Haskell, return `Nothing`; in Fortran, return `0`; in Go, return an error)

### Examples

```python
solve("((1)23(45))(aB)", 0) = 10 -- the opening brace at index 0 matches the closing brace at index 10
solve("((1)23(45))(aB)", 1) = 3 
solve("((1)23(45))(aB)", 2) = -1 -- there is no opening bracket at index 2, so return -1
solve("((1)23(45))(aB)", 6) = 9
solve("((1)23(45))(aB)", 11) = 14
solve("((>)|?(*'))(yZ)", 11) = 14
```

Input will consist of letters, numbers and special characters, but no spaces. The only brackets will be `(` and `)`. 

More examples in the test cases. 

Good luck!

~~~if:fortran
*NOTE: In Fortran, you may assume that the input string will not contain any leading/trailing whitespace.*
~~~

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One of the most well-known and classic methods of encryption is the Vigenère cipher. Given a message and key of equal length, all you need to do to encrypt the message is shift each character forward by a certain number of characters in the alphabet.

For example, if your string is CALGARY and key is ALBERTA, the number of letters to shift the $i$-th letter in the message is given by the position in the alphabet of the $i$-th letter in the key, using $0$-based indexing. So the first character in our message C is shifted $0$ letters forward since the first character in our key is A. Likewise, A is shifted $11$ characters since L is the $11$-th letter in the alphabet. Repeating for each character, we’ll find the encrypted message ends up being CLMKRKY.

Of course since this is such a well known encryption method, it isn’t very safe so your friend Yraglac has come up with a brilliant idea: for each even-indexed character in your message, you do the usual encryption as described above, but for the odd-indexed characters, instead of shifting forwards by the key, you actually shift backwards. Thus, our example above would actually be encrypted as CPMCRYY. That’ll throw off any pesky hackers trying to read your secrets!

Of course Yraglac has left the implementation up to you. Given an encrypted message and the key, can you write a program to decrypt it? Don’t forget that everything is using $0$-based indexing.

-----Input-----
Input consists of two lines. The first contains the encrypted message $C$ and the second contains the key $K$. $C$ and $K$ are always of equal length between $1$ and $200$ characters long and consists only of uppercase alphabetic letters.

-----Output-----
Output the decrypted message.

-----Examples-----
Sample Input:
CPMCRYY
ALBERTA
Sample Output:
CALGARY

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is an area map that is a rectangular matrix n × m, each cell of the matrix contains the average height of a corresponding area part. Peter works for a company that has to build several cities within this area, each of the cities will occupy a rectangle a × b cells on the map. To start construction works in a particular place Peter needs to remove excess ground from the construction site where a new city will be built. To do so he chooses a cell of the minimum height within this site, and removes excess ground from other cells of the site down to this minimum level. Let's consider that to lower the ground level from h2 to h1 (h1 ≤ h2) they need to remove h2 - h1 ground units.

Let's call a site's position optimal, if the amount of the ground removed from this site is minimal compared to other possible positions. Peter constructs cities according to the following algorithm: from all the optimum site's positions he chooses the uppermost one. If this position is not unique, he chooses the leftmost one. Then he builds a city on this site. Peter repeats this process untill he can build at least one more city. For sure, he cannot carry out construction works on the occupied cells. Would you, please, help Peter place cities according to the algorithm? 

Input

The first line contains four space-separated integers: map sizes n, m and city sizes a, b (1 ≤ a ≤ n ≤ 1000, 1 ≤ b ≤ m ≤ 1000). Then there follow n lines, each contains m non-negative space-separated numbers, describing the height matrix. Each number doesn't exceed 109. 

Output

In the first line output k — the amount of constructed cities. In each of the following k lines output 3 space-separated numbers — the row number and the column number of the upper-left corner of a subsequent construction site, and the amount of the ground to remove from it. Output the sites in the order of their building up.

Examples

Input

2 2 1 2
1 2
3 5


Output

2
1 1 1
2 1 2


Input

4 4 2 2
1 5 3 4
2 7 6 1
1 1 2 2
2 2 1 2


Output

3
3 1 2
3 3 3
1 2 9

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Some people leave the lights at their workplaces on when they leave that is a waste of resources. As a hausmeister of DHBW, Sagheer waits till all students and professors leave the university building, then goes and turns all the lights off.

The building consists of *n* floors with stairs at the left and the right sides. Each floor has *m* rooms on the same line with a corridor that connects the left and right stairs passing by all the rooms. In other words, the building can be represented as a rectangle with *n* rows and *m*<=+<=2 columns, where the first and the last columns represent the stairs, and the *m* columns in the middle represent rooms.

Sagheer is standing at the ground floor at the left stairs. He wants to turn all the lights off in such a way that he will not go upstairs until all lights in the floor he is standing at are off. Of course, Sagheer must visit a room to turn the light there off. It takes one minute for Sagheer to go to the next floor using stairs or to move from the current room/stairs to a neighboring room/stairs on the same floor. It takes no time for him to switch the light off in the room he is currently standing in. Help Sagheer find the minimum total time to turn off all the lights.

Note that Sagheer does not have to go back to his starting position, and he does not have to visit rooms where the light is already switched off.

Input Specification:
The first line contains two integers *n* and *m* (1<=≤<=*n*<=≤<=15 and 1<=≤<=*m*<=≤<=100) — the number of floors and the number of rooms in each floor, respectively.

The next *n* lines contains the building description. Each line contains a binary string of length *m*<=+<=2 representing a floor (the left stairs, then *m* rooms, then the right stairs) where 0 indicates that the light is off and 1 indicates that the light is on. The floors are listed from top to bottom, so that the last line represents the ground floor.

The first and last characters of each string represent the left and the right stairs, respectively, so they are always 0.

Output Specification:
Print a single integer — the minimum total time needed to turn off all the lights.

Demo Input:
['2 2\n0010\n0100\n', '3 4\n001000\n000010\n000010\n', '4 3\n01110\n01110\n01110\n01110\n']

Demo Output:
['5\n', '12\n', '18\n']

Note:
In the first example, Sagheer will go to room 1 in the ground floor, then he will go to room 2 in the second floor using the left or right stairs.

In the second example, he will go to the fourth room in the ground floor, use right stairs, go to the fourth room in the second floor, use right stairs again, then go to the second room in the last floor.

In the third example, he will walk through the whole corridor alternating between the left and right stairs at each floor.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the wake of the npm's `left-pad` debacle, you decide to write a new super padding method that superceds the functionality of `left-pad`. Your version will provide the same functionality, but will additionally add right, and justified padding of string -- the `super_pad`.

Your function `super_pad` should take three arguments: the string `string`, the width of the final string `width`, and a fill character `fill`. However, the fill character can be enriched with a format string resulting in different padding strategies. If `fill` begins with `'<'` the string is padded on the left with the remaining fill string and if `fill` begins with `'>'` the string is padded on the right. Finally, if `fill` begins with `'^'` the string is padded on the left and the right, where the left padding is always greater or equal to the right padding. The `fill` string can contain more than a single char, of course. 

Some examples to clarify the inner workings:

- `super_pad("test", 10)` returns "      test"
- `super_pad("test", 10, "x")` returns `"xxxxxxtest"`
- `super_pad("test", 10, "xO")` returns `"xOxOxOtest"`
- `super_pad("test", 10, "xO-")` returns `"xO-xO-test"`
- `super_pad("some other test", 10, "nope")` returns `"other test"`
- `super_pad("some other test", 10, "> ")` returns `"some other"`
- `super_pad("test", 7, ">nope")` returns `"testnop"`
- `super_pad("test", 7, "^more complex")` returns `"motestm"`
- `super_pad("test", 7, "")` returns `"test"`

The `super_pad` method always returns a string of length `width` if possible. We expect the `width` to be positive (including 0) and the fill could be also an empty string.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Companies always have a lot of equipment, furniture and other things. All of them should be tracked. To do this, there is an inventory number assigned with each item. It is much easier to create a database by using those numbers and keep the track of everything.

During an audit, you were surprised to find out that the items are not numbered sequentially, and some items even share the same inventory number! There is an urgent need to fix it. You have chosen to make the numbers of the items sequential, starting with 1. Changing a number is quite a time-consuming process, and you would like to make maximum use of the current numbering.

You have been given information on current inventory numbers for *n* items in the company. Renumber items so that their inventory numbers form a permutation of numbers from 1 to *n* by changing the number of as few items as possible. Let us remind you that a set of *n* numbers forms a permutation if all the numbers are in the range from 1 to *n*, and no two numbers are equal.

Input Specification:
The first line contains a single integer *n* — the number of items (1<=≤<=*n*<=≤<=105).

The second line contains *n* numbers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=105) — the initial inventory numbers of the items.

Output Specification:
Print *n* numbers — the final inventory numbers of the items in the order they occur in the input. If there are multiple possible answers, you may print any of them.

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

Demo Output:
['1 3 2 \n', '2 1 3 4 \n', '1 \n']

Note:
In the first test the numeration is already a permutation, so there is no need to change anything.

In the second test there are two pairs of equal numbers, in each pair you need to replace one number.

In the third test you need to replace 2 by 1, as the numbering should start from one.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pashmak has fallen in love with an attractive girl called Parmida since one year ago...

Today, Pashmak set up a meeting with his partner in a romantic garden. Unfortunately, Pashmak has forgotten where the garden is. But he remembers that the garden looks like a square with sides parallel to the coordinate axes. He also remembers that there is exactly one tree on each vertex of the square. Now, Pashmak knows the position of only two of the trees. Help him to find the position of two remaining ones.


-----Input-----

The first line contains four space-separated x_1, y_1, x_2, y_2 ( - 100 ≤ x_1, y_1, x_2, y_2 ≤ 100) integers, where x_1 and y_1 are coordinates of the first tree and x_2 and y_2 are coordinates of the second tree. It's guaranteed that the given points are distinct.


-----Output-----

If there is no solution to the problem, print -1. Otherwise print four space-separated integers x_3, y_3, x_4, y_4 that correspond to the coordinates of the two other trees. If there are several solutions you can output any of them. 

Note that x_3, y_3, x_4, y_4 must be in the range ( - 1000 ≤ x_3, y_3, x_4, y_4 ≤ 1000).


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

Output
1 0 1 1

Input
0 0 1 1

Output
0 1 1 0

Input
0 0 1 2

Output
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A social network for dogs called DH (DogHouse) has k special servers to recompress uploaded videos of cute cats. After each video is uploaded, it should be recompressed on one (any) of the servers, and only after that it can be saved in the social network.

We know that each server takes one second to recompress a one minute fragment. Thus, any server takes m seconds to recompress a m minute video.

We know the time when each of the n videos were uploaded to the network (in seconds starting from the moment all servers started working). All videos appear at different moments of time and they are recompressed in the order they appear. If some video appeared at time s, then its recompressing can start at that very moment, immediately. Some videos can await recompressing when all the servers are busy. In this case, as soon as a server is available, it immediately starts recompressing another video. The videos that await recompressing go in a queue. If by the moment the videos started being recompressed some servers are available, then any of them starts recompressing the video.

For each video find the moment it stops being recompressed.


-----Input-----

The first line of the input contains integers n and k (1 ≤ n, k ≤ 5·10^5) — the number of videos and servers, respectively.

Next n lines contain the descriptions of the videos as pairs of integers s_{i}, m_{i} (1 ≤ s_{i}, m_{i} ≤ 10^9), where s_{i} is the time in seconds when the i-th video appeared and m_{i} is its duration in minutes. It is guaranteed that all the s_{i}'s are distinct and the videos are given in the chronological order of upload, that is in the order of increasing s_{i}.


-----Output-----

Print n numbers e_1, e_2, ..., e_{n}, where e_{i} is the time in seconds after the servers start working, when the i-th video will be recompressed.


-----Examples-----
Input
3 2
1 5
2 5
3 5

Output
6
7
11

Input
6 1
1 1000000000
2 1000000000
3 1000000000
4 1000000000
5 1000000000
6 3

Output
1000000001
2000000001
3000000001
4000000001
5000000001
5000000004

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