vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
In this problem your goal is to sort an array consisting of n integers in at most n swaps. For the given array find the sequence of swaps that makes the array sorted in the non-descending order. Swaps are performed consecutively, one after another.

Note that in this problem you do not have to minimize the number of swaps — your task is to find any sequence that is no longer than n.


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 3000) — the number of array elements. The second line contains elements of array: a_0, a_1, ..., a_{n} - 1 ( - 10^9 ≤ a_{i} ≤ 10^9), where a_{i} is the i-th element of the array. The elements are numerated from 0 to n - 1 from left to right. Some integers may appear in the array more than once.


-----Output-----

In the first line print k (0 ≤ k ≤ n) — the number of swaps. Next k lines must contain the descriptions of the k swaps, one per line. Each swap should be printed as a pair of integers i, j (0 ≤ i, j ≤ n - 1), representing the swap of elements a_{i} and a_{j}. You can print indices in the pairs in any order. The swaps are performed in the order they appear in the output, from the first to the last. It is allowed to print i = j and swap the same pair of elements multiple times.

If there are multiple answers, print any of them. It is guaranteed that at least one answer exists.


-----Examples-----
Input
5
5 2 5 1 4

Output
2
0 3
4 2

Input
6
10 20 20 40 60 60

Output
0

Input
2
101 100

Output
1
0 1

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

Time Limit: 1 seconds

Memory Limit: 64 megabytes

Problem Description:
The main server of Gomble company received a log of one top-secret process, the name of which can't be revealed. The log was written in the following format: «[date:time]: message», where for each «[date:time]» value existed not more than 10 lines. All the files were encoded in a very complicated manner, and only one programmer — Alex — managed to decode them. The code was so complicated that Alex needed four weeks to decode it. Right after the decoding process was finished, all the files were deleted. But after the files deletion, Alex noticed that he saved the recordings in format «[time]: message». So, information about the dates was lost. However, as the lines were added into the log in chronological order, it's not difficult to say if the recordings could appear during one day or not. It is possible also to find the minimum amount of days during which the log was written.

So, to make up for his mistake Alex has to find the minimum amount of days covered by the log. Note that Alex doesn't have to find the minimum amount of days between the beginning and the end of the logging, he has to find the minimum amount of dates in which records could be done. (See Sample test 2 for further clarifications).

We should remind you that the process made not more than 10 recordings in a minute. Consider that a midnight belongs to coming day.

Input Specification:
The first input line contains number *n* (1<=≤<=*n*<=≤<=100). The following *n* lines contain recordings in format «[time]: message», where time is given in format «hh:mm x.m.». For hh two-digit numbers from 01 to 12 are used, for mm two-digit numbers from 00 to 59 are used, and x is either character «a» or character «p». A message is a non-empty sequence of Latin letters and/or spaces, it doesn't start or end with a space. The length of each message doesn't exceed 20.

Output Specification:
Output one number — the minimum amount of days covered by the log.

Demo Input:
['5\n[05:00 a.m.]: Server is started\n[05:00 a.m.]: Rescan initialized\n[01:13 p.m.]: Request processed\n[01:10 p.m.]: Request processed\n[11:40 p.m.]: Rescan completed\n', '3\n[09:00 a.m.]: User logged in\n[08:00 a.m.]: User logged in\n[07:00 a.m.]: User logged in\n']

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

Note:
Formally the 12-hour time format is described at: 
 -  http://en.wikipedia.org/wiki/12-hour_clock.

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

The zeros tool returns a new array with a given shape and type filled with $\mbox{o}$'s.

import numpy

print numpy.zeros((1,2))                    #Default type is float
#Output : [[ 0.  0.]] 

print numpy.zeros((1,2), dtype = numpy.int) #Type changes to int
#Output : [[0 0]]

ones

The ones tool returns a new array with a given shape and type filled with $\mbox{I}$'s.

import numpy

print numpy.ones((1,2))                    #Default type is float
#Output : [[ 1.  1.]] 

print numpy.ones((1,2), dtype = numpy.int) #Type changes to int
#Output : [[1 1]]   

Task  

You are given the shape of the array in the form of space-separated integers, each integer representing the size of different dimensions, your task is to print an array of the given shape and integer type using the tools numpy.zeros and numpy.ones.

Input Format

A single line containing the space-separated integers.

Constraints

$1\leq\text{each integer}\leq3$

Output Format

First, print the array using the numpy.zeros tool and then print the array with the numpy.ones tool.  

Sample Input 0
3 3 3

Sample Output 0
[[[0 0 0]
  [0 0 0]
  [0 0 0]]

 [[0 0 0]
  [0 0 0]
  [0 0 0]]

 [[0 0 0]
  [0 0 0]
  [0 0 0]]]
[[[1 1 1]
  [1 1 1]
  [1 1 1]]

 [[1 1 1]
  [1 1 1]
  [1 1 1]]

 [[1 1 1]
  [1 1 1]
  [1 1 1]]]

Explanation 0

Print the array built using numpy.zeros and numpy.ones tools and you get the result as shown.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two huge binary integer numbers $a$ and $b$ of lengths $n$ and $m$ respectively. You will repeat the following process: if $b > 0$, then add to the answer the value $a~ \&~ b$ and divide $b$ by $2$ rounding down (i.e. remove the last digit of $b$), and repeat the process again, otherwise stop the process.

The value $a~ \&~ b$ means bitwise AND of $a$ and $b$. Your task is to calculate the answer modulo $998244353$.

Note that you should add the value $a~ \&~ b$ to the answer in decimal notation, not in binary. So your task is to calculate the answer in decimal notation. For example, if $a = 1010_2~ (10_{10})$ and $b = 1000_2~ (8_{10})$, then the value $a~ \&~ b$ will be equal to $8$, not to $1000$.


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the length of $a$ and the length of $b$ correspondingly.

The second line of the input contains one huge integer $a$. It is guaranteed that this number consists of exactly $n$ zeroes and ones and the first digit is always $1$.

The third line of the input contains one huge integer $b$. It is guaranteed that this number consists of exactly $m$ zeroes and ones and the first digit is always $1$.


-----Output-----

Print the answer to this problem in decimal notation modulo $998244353$.


-----Examples-----
Input
4 4
1010
1101

Output
12

Input
4 5
1001
10101

Output
11



-----Note-----

The algorithm for the first example:   add to the answer $1010_2~ \&~ 1101_2 = 1000_2 = 8_{10}$ and set $b := 110$;  add to the answer $1010_2~ \&~ 110_2 = 10_2 = 2_{10}$ and set $b := 11$;  add to the answer $1010_2~ \&~ 11_2 = 10_2 = 2_{10}$ and set $b := 1$;  add to the answer $1010_2~ \&~ 1_2 = 0_2 = 0_{10}$ and set $b := 0$. 

So the answer is $8 + 2 + 2 + 0 = 12$.

The algorithm for the second example:   add to the answer $1001_2~ \&~ 10101_2 = 1_2 = 1_{10}$ and set $b := 1010$;  add to the answer $1001_2~ \&~ 1010_2 = 1000_2 = 8_{10}$ and set $b := 101$;  add to the answer $1001_2~ \&~ 101_2 = 1_2 = 1_{10}$ and set $b := 10$;  add to the answer $1001_2~ \&~ 10_2 = 0_2 = 0_{10}$ and set $b := 1$;  add to the answer $1001_2~ \&~ 1_2 = 1_2 = 1_{10}$ and set $b := 0$. 

So the answer is $1 + 8 + 1 + 0 + 1 = 11$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You know that Japan is the country with almost the largest 'electronic devices per person' ratio. So you might be quite surprised to find out that the primary school in Japan teaches to count using a Soroban — an abacus developed in Japan. This phenomenon has its reasons, of course, but we are not going to speak about them. Let's have a look at the Soroban's construction.

<image>

Soroban consists of some number of rods, each rod contains five beads. We will assume that the rods are horizontal lines. One bead on each rod (the leftmost one) is divided from the others by a bar (the reckoning bar). This single bead is called go-dama and four others are ichi-damas. Each rod is responsible for representing a single digit from 0 to 9. We can obtain the value of a digit by following simple algorithm:

  * Set the value of a digit equal to 0. 
  * If the go-dama is shifted to the right, add 5. 
  * Add the number of ichi-damas shifted to the left. 



Thus, the upper rod on the picture shows digit 0, the middle one shows digit 2 and the lower one shows 7. We will consider the top rod to represent the last decimal digit of a number, so the picture shows number 720.

Write the program that prints the way Soroban shows the given number n.

Input

The first line contains a single integer n (0 ≤ n < 109).

Output

Print the description of the decimal digits of number n from the last one to the first one (as mentioned on the picture in the statement), one per line. Print the beads as large English letters 'O', rod pieces as character '-' and the reckoning bar as '|'. Print as many rods, as many digits are in the decimal representation of number n without leading zeroes. We can assume that number 0 has no leading zeroes.

Examples

Input

2


Output

O-|OO-OO


Input

13


Output

O-|OOO-O
O-|O-OOO


Input

720


Output

O-|-OOOO
O-|OO-OO
-O|OO-OO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bear Limak wants to become the largest of bears, or at least to become larger than his brother Bob.

Right now, Limak and Bob weigh a and b respectively. It's guaranteed that Limak's weight is smaller than or equal to his brother's weight.

Limak eats a lot and his weight is tripled after every year, while Bob's weight is doubled after every year.

After how many full years will Limak become strictly larger (strictly heavier) than Bob?


-----Input-----

The only line of the input contains two integers a and b (1 ≤ a ≤ b ≤ 10) — the weight of Limak and the weight of Bob respectively.


-----Output-----

Print one integer, denoting the integer number of years after which Limak will become strictly larger than Bob.


-----Examples-----
Input
4 7

Output
2

Input
4 9

Output
3

Input
1 1

Output
1



-----Note-----

In the first sample, Limak weighs 4 and Bob weighs 7 initially. After one year their weights are 4·3 = 12 and 7·2 = 14 respectively (one weight is tripled while the other one is doubled). Limak isn't larger than Bob yet. After the second year weights are 36 and 28, so the first weight is greater than the second one. Limak became larger than Bob after two years so you should print 2.

In the second sample, Limak's and Bob's weights in next years are: 12 and 18, then 36 and 36, and finally 108 and 72 (after three years). The answer is 3. Remember that Limak wants to be larger than Bob and he won't be satisfied with equal weights.

In the third sample, Limak becomes larger than Bob after the first year. Their weights will be 3 and 2 then.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a positive integer N, find the sum of all prime numbers between 1 and N(inclusive).
 
Example 1:
Input: N = 5
Output: 10
Explanation: 2, 3, and 5 are prime
numbers between 1 and 5(inclusive).
Example 2:
Input: N = 10
Output: 17
Explanation: 2, 3, 5 and 7 are prime
numbers between 1 and 10(inclusive).
 
Your Task:
You don't need to read or print anything. Your task is to complete the function prime_Sum() which takes N as input parameter and returns the sum of all primes between 1 and N(inclusive).
 
Expected Time Complexity: O(N*log(N))
Expected Space Complexity: O(N)
Constraints:
1 <= N <= 1000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Even polar bears feel cold when lying on the ice. Therefore, a polar bear Alice is going to make a carpet. The carpet can be viewed as a grid with height h and width w. Then the grid is divided into h × w squares. Alice is going to assign one of k different colors to each square. The colors are numbered from 1 to k. She may choose not to use all of the colors.

However, there are some restrictions. For every two adjacent squares (squares that shares an edge) x and y, there is a color constraint in one of the forms: 

  * color(x) = color(y), or 
  * color(x) ≠ color(y). 



Example of the color constraints:

<image>

Ideally, Alice wants to satisfy all color constraints. But again, life in the Arctic is hard. It is not always possible to satisfy all color constraints. Fortunately, she will still be happy if at least <image> of the color constraints are satisfied. 

If she has 4 colors she can color the carpet in the following way:

<image>

And she is happy because <image> of the color constraints are satisfied, and <image>. Your task is to help her color the carpet.

Input

The first line contains three integers h, w, k (2 ≤ h, w ≤ 1000, 1 ≤ k ≤ w·h).

The next 2h - 1 lines describe the color constraints from top to bottom, left to right. They contain w - 1, w, w - 1, w, ..., w - 1 characters respectively. Each color constraint is represented by a character "E" or "N", where "E" means " = " and "N" means " ≠ ".

The color constraints listed in the order they are depicted on the picture.

Output

If there is a coloring that satisfies at least <image> of the color constraints, print "YES" (without quotes) in the first line. In each of the next h lines, print w integers describing the coloring.

Otherwise, print "NO" (without quotes).

Examples

Input

3 4 4
ENE
NNEE
NEE
ENEN
ENN


Output

YES
1 1 2 2
3 4 1 1
3 3 2 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After finding a suitable residence in the Swiss Alps, Robin thought he finally had what it takes to be happy. But every day he woke up feeling that something was missing. Maybe it was the lack of English food in these parts? Spotting a market opportunity and solving his problem at the same time, he teamed up with the famous English chef Jim to open a restaurant nearby. While he has no doubts about Jim’s talents as a chef, Robin wants to be sure that opening an English restaurant in the Swiss Alps is a good idea.

Fortunately, as a local, he knows the habits of restaurant customers. At the stroke of each hour, a group of people arrives of size that is uniformly random between $1$ and $g$ people (inclusive). The group finds the smallest completely unoccupied table that fits the group and occupies it. If they can not find such a table, the group leaves with great disappointment. Once seated, a group never leaves until the restaurant closes, as Jim has no difficulty keeping the guests entertained.

As an example, suppose the restaurant has $3$ tables of capacities $5$, $8$ and $9$. If groups of sizes $5, 10$ and $3$ arrive (in that order), in the end there will be $8$ people in the restaurant. The first group occupies the table of capacity $5$, the second group leaves and the last group occupies the table of capacity $8$.

Robin plans to keep his restaurant open for $t$ hours in total. In the restaurant business the most important metric is the expected number of people in the restaurant when it is closes. Can you help Robin calculate the expected occupancy after $t$ hours?

-----Input-----
The input consists of:
 - One line with three integers $n, g, t$ ($1 \le n \le 100, 1\leq g\leq 200, 1\leq t \leq 100$), the number of tables in the restaurant, the maximum group size, and the number of hours the restaurant is open.
 - One line with $n$ integers $c_1, \ldots , c_ n$ ($1 \le c_ i \le 200$ for each $i$) giving the capacities of the tables.

-----Output-----
Output the expected number of people in the restaurant when it closes. Your answer should have an absolute or relative error of at most $10^{-6}$.

-----Examples-----
Sample Input 1:
3 3 2
1 2 3
Sample Output 1:
3.666666667

Sample Input 2:
4 11 4
10 10 10 10
Sample Output 2:
20.000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer N.Create a string using only lowercase characters from a to z that follows the given rules.
When N is even:
Use N/2 characters from the beginning of a-z and N/2 characters from the ending of a-z.
When N is greater than 26,continue repeating the instructions until length of string becomes N.
When N is odd:
Case 1: If the sum of digits of N is even, Select (N+1)/2 characters from the beginning of a-z and (N-1)/2 characters from the ending of a-z.
Case 2: If the sum of digits of N is odd, Select (N-1)/2 characters from the beginning of a-z and (N+1)/2 characters from the ending of a-z.
When N is greater than 26,continue repeating the instructions until length of string becomes N.
 
Example 1:
Input: 
N=21
Output: 
abcdefghijpqrstuvwxyz
Explanation:
Since 21 is odd and sum of digits
of 21 is also odd,we take (21-1)/2=10 
characters from the beginning and 
(21+1)/2=11 characters from the 
end of a-z.
Example 2: 
Input:
N=28 
Output: 
abcdefghijklmnopqrstuvwxyzaz
Explanation: 
Since 28>26, we keep repeating 
the process until length of string becomes 
28.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function BalancedString() which takes the integer N as input parameter and returns the string created using given procedures.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{5}

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

Time Limit: 1 seconds

Memory Limit: 256 megabytes

Problem Description:
Vasya’s elder brother Petya loves playing computer games. In one of his favourite computer games Petya reached the final level where a fight with the boss take place.

While playing the game Petya found spell scrolls and now he is about to use them. Let’s describe the way fighting goes on this level:

1) The boss has two parameters: *max* — the initial amount of health and *reg* — regeneration rate per second.

2) Every scroll also has two parameters: *pow**i* — spell power measured in percents — the maximal amount of health counted off the initial one, which allows to use the scroll (i.e. if the boss has more than *pow**i* percent of health the scroll cannot be used); and *dmg**i* the damage per second inflicted upon the boss if the scroll is used. As soon as a scroll is used it disappears and another spell is cast upon the boss that inflicts *dmg**i* of damage per second upon him until the end of the game.

During the battle the actions per second are performed in the following order: first the boss gets the damage from all the spells cast upon him, then he regenerates *reg* of health (at the same time he can’t have more than *max* of health), then the player may use another scroll (no more than one per second).

The boss is considered to be defeated if at the end of a second he has nonpositive (<=≤<=0) amount of health.

Help Petya to determine whether he can win with the set of scrolls available to him and if he can, determine the minimal number of seconds he needs to do it.

Input Specification:
The first line contains three integers *N*, *max* and *reg* (1<=≤<=*N*,<=*max*,<=*reg*<=≤<=1000) –– the amount of scrolls and the parameters of the boss. The next *N* lines contain two integers *pow**i* and *dmg**i* each — the parameters of the *i*-th scroll (0<=≤<=*pow**i*<=≤<=100, 1<=≤<=*dmg**i*<=≤<=2000).

Output Specification:
In case Petya can’t complete this level, output in the single line NO.

Otherwise, output on the first line YES. On the second line output the minimal time after which the boss can be defeated and the number of used scrolls. In the next lines for each used scroll output space-separated number of seconds passed from the start of the battle to the moment the scroll was used and the number of the scroll. Scrolls are numbered starting from 1 in the input order. The first scroll is considered to be available to be used after 0 seconds.

Output scrolls in the order they were used. It is not allowed to use scrolls after the boss is defeated.

Demo Input:
['2 10 3\n100 3\n99 1\n', '2 100 10\n100 11\n90 9\n']

Demo Output:
['NO\n', 'YES\n19 2\n0 1\n10 2\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array A of size N, construct a Sum Array S(of same size) such that S is equal to the sum of all the elements of A except A[i]. Your task is to complete the function SumArray(A, N) which accepts the array A and N(size of array). 
Example 1:
Input:
5
3 6 4 8 9
Output: 27 24 26 22 21
Explanation: For the sum array S, at i=0 we
have 6+4+8+9. At i=1, 3+4+8+9. At i=2, we 
have 3+6+8+9. At i=3, we have 3+6+4+9. At
i = 4, we have 3+6+4+8. So S is 27 24 26 22 21.
Example 2:
Input:
6
4 5 7 3 10 1
Output: 26 25 23 27 20 29 
User Task:
Since this is a functional problem you did not have to worry about the input and output. You just have to complete the function SumArray() by storing arr[i]=S-arr[i]
Constraint :
1 <= T <= 10
1 <= N <= 10^{4}
1 <= A_{i} <= 10^{4}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider packing widgets for shipping where widgets cannot be stacked upon each other (2D packing). Each widget has a $1\times ~ l$ footprint and is $1$ unit high.

Boxes are available in any $W$ by $H$ by $1$ size such that $H/2 \leq W \leq 2H$, with $W$ and $H$ being integers. The company wants to minimize the amount of packing material that will be needed to fill empty squares in a box.

Given $N$, the number of widgets to be shipped, what is the smallest number of squares that will be left empty when those widgets are packed for shipping?

-----Input-----
Input consists of one line containing an integer $N$, the number of widgets to be packed, where $1 \leq N \leq 10^{16}$.

-----Output-----
Print a single line containing an integer denoting the minimum number of empty squares.

-----Examples-----
Sample Input 1:
47
Sample Output 1:
1

Sample Input 2:
523
Sample Output 2:
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
People do many crazy things to stand out in a crowd. Some of them dance, some learn by heart rules of Russian language, some try to become an outstanding competitive programmers, while others collect funny math objects.

Alis is among these collectors. Right now she wants to get one of k-special tables. In case you forget, the table n × n is called k-special if the following three conditions are satisfied:  every integer from 1 to n^2 appears in the table exactly once;  in each row numbers are situated in increasing order;  the sum of numbers in the k-th column is maximum possible. 

Your goal is to help Alice and find at least one k-special table of size n × n. Both rows and columns are numbered from 1 to n, with rows numbered from top to bottom and columns numbered from left to right.


-----Input-----

The first line of the input contains two integers n and k (1 ≤ n ≤ 500, 1 ≤ k ≤ n) — the size of the table Alice is looking for and the column that should have maximum possible sum.


-----Output-----

First print the sum of the integers in the k-th column of the required table.

Next n lines should contain the description of the table itself: first line should contains n elements of the first row, second line should contain n elements of the second row and so on.

If there are multiple suitable table, you are allowed to print any.


-----Examples-----
Input
4 1

Output
28
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Input
5 3

Output
85
5 6 17 18 19
9 10 23 24 25
7 8 20 21 22
3 4 14 15 16
1 2 11 12 13

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