vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
In Insertion Sort Part 1, you inserted one element into an array at its correct sorted position. Using the same approach repeatedly, can you sort an entire array?

Guideline: You already can place an element into a sorted array. How can you use that code to build up a sorted array, one element at a time? Note that in the first step, when you consider an array with just the first element, it is already sorted since there's nothing to compare it to.

In this challenge, print the array after each iteration of the insertion sort, i.e., whenever the next element has been inserted at its correct position.  Since the array composed of just the first element is already sorted, begin printing after placing the second element.

Example. 

$n=7$ 

$arr=[3,4,7,5,6,2,1]$   

Working from left to right, we get the following output:

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

Function Description

Complete the insertionSort2 function in the editor below.  

insertionSort2 has the following parameter(s):  

int n: the length of $\textbf{arr}$  
int arr[n]: an array of integers  

Prints  

At each iteration, print the array as space-separated integers on its own line.  

Input Format

The first line contains an integer, $n$, the size of $\textbf{arr}$. 

 The next line contains $n$ space-separated integers $arr\left[i\right]$.  

Constraints

$1\leq n\leq1000$ 

$-10000\leq arr[i]\leq10000,0\leq i\lt n$ 

Output Format

Print the entire array on a new line at every iteration.

Sample Input
STDIN           Function
-----           --------
6               n = 6
1 4 3 5 6 2     arr = [1, 4, 3, 5, 6, 2]

Sample Output
1 4 3 5 6 2 
1 3 4 5 6 2 
1 3 4 5 6 2 
1 3 4 5 6 2 
1 2 3 4 5 6 

Explanation

Skip testing $\mbox{1}$ against itself at position $\mbox{0}$.  It is sorted. 

Test position $\mbox{1}$ against position $\mbox{0}$: $4>1$, no more to check, no change. 

Print $\textbf{arr}$ 

Test position $2$ against positions $\mbox{1}$ and $\mbox{0}$: 

$3<4$, new position may be $\mbox{1}$.  Keep checking.    
$3>1$, so insert $3$ at position $\mbox{1}$ and move others to the right.   

Print $\textbf{arr}$ 

Test position $3$ against positions $2,1,0$ (as necessary): no change. 

Print $\textbf{arr}$ 

Test position $\begin{array}{c}4\end{array}$ against positions $3,2,1,0$: no change. 

Print $\textbf{arr}$ 

Test position $5$ against positions $4,3,2,1,0$, insert $2$ at position $\mbox{1}$ and move others to the right. 

Print $\textbf{arr}$

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are *n* boxes with colored balls on the table. Colors are numbered from 1 to *n*. *i*-th box contains *a**i* balls, all of which have color *i*. You have to write a program that will divide all balls into sets such that:
 -  each ball belongs to exactly one of the sets, -  there are no empty sets, -  there is no set containing two (or more) balls of different colors (each set contains only balls of one color), -  there are no two sets such that the difference between their sizes is greater than 1. 
Print the minimum possible number of sets.

Input Specification:
The first line contains one integer number *n* (1<=≤<=*n*<=≤<=500).

The second line contains *n* integer numbers *a*1,<=*a*2,<=... ,<=*a**n* (1<=≤<=*a**i*<=≤<=109).

Output Specification:
Print one integer number — the minimum possible number of sets.

Demo Input:
['3\n4 7 8\n', '2\n2 7\n']

Demo Output:
['5\n', '4\n']

Note:
In the first example the balls can be divided into sets like that: one set with 4 balls of the first color, two sets with 3 and 4 balls, respectively, of the second color, and two sets with 4 balls of the third color.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Hongcow likes solving puzzles.

One day, Hongcow finds two identical puzzle pieces, with the instructions "make a rectangle" next to them. The pieces can be described by an n by m grid of characters, where the character 'X' denotes a part of the puzzle and '.' denotes an empty part of the grid. It is guaranteed that the puzzle pieces are one 4-connected piece. See the input format and samples for the exact details on how a jigsaw piece will be specified.

The puzzle pieces are very heavy, so Hongcow cannot rotate or flip the puzzle pieces. However, he is allowed to move them in any directions. The puzzle pieces also cannot overlap.

You are given as input the description of one of the pieces. Determine if it is possible to make a rectangle from two identical copies of the given input. The rectangle should be solid, i.e. there should be no empty holes inside it or on its border. Keep in mind that Hongcow is not allowed to flip or rotate pieces and they cannot overlap, i.e. no two 'X' from different pieces can share the same position.


-----Input-----

The first line of input will contain two integers n and m (1 ≤ n, m ≤ 500), the dimensions of the puzzle piece.

The next n lines will describe the jigsaw piece. Each line will have length m and will consist of characters '.' and 'X' only. 'X' corresponds to a part of the puzzle piece, '.' is an empty space.

It is guaranteed there is at least one 'X' character in the input and that the 'X' characters form a 4-connected region.


-----Output-----

Output "YES" if it is possible for Hongcow to make a rectangle. Output "NO" otherwise.


-----Examples-----
Input
2 3
XXX
XXX

Output
YES

Input
2 2
.X
XX

Output
NO

Input
5 5
.....
..X..
.....
.....
.....

Output
YES



-----Note-----

For the first sample, one example of a rectangle we can form is as follows 

111222

111222



For the second sample, it is impossible to put two of those pieces without rotating or flipping to form a rectangle.

In the third sample, we can shift the first tile by one to the right, and then compose the following rectangle: 

.....

..XX.

.....

.....

.....

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Professor GukiZ likes programming contests. He especially likes to rate his students on the contests he prepares. Now, he has decided to prepare a new contest. 

In total, *n* students will attend, and before the start, every one of them has some positive integer rating. Students are indexed from 1 to *n*. Let's denote the rating of *i*-th student as *a**i*. After the contest ends, every student will end up with some positive integer position. GukiZ expects that his students will take places according to their ratings. 

He thinks that each student will take place equal to . In particular, if student *A* has rating strictly lower then student *B*, *A* will get the strictly better position than *B*, and if two students have equal ratings, they will share the same position. 

GukiZ would like you to reconstruct the results by following his expectations. Help him and determine the position after the end of the contest for each of his students if everything goes as expected.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=2000), number of GukiZ's students. 

The second line contains *n* numbers *a*1,<=*a*2,<=... *a**n* (1<=≤<=*a**i*<=≤<=2000) where *a**i* is the rating of *i*-th student (1<=≤<=*i*<=≤<=*n*).

Output Specification:
In a single line, print the position after the end of the contest for each of *n* students in the same order as they appear in the input.

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

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

Note:
In the first sample, students 2 and 3 are positioned first (there is no other student with higher rating), and student 1 is positioned third since there are two students with higher rating.

In the second sample, first student is the only one on the contest.

In the third sample, students 2 and 5 share the first position with highest rating, student 4 is next with third position, and students 1 and 3 are the last sharing fourth position.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kate and Michael want to buy a pizza and share it. Depending on the price of the pizza, they are going to divide the costs:

* If the pizza is less than €5,- Michael invites Kate, so Michael pays the full price.
* Otherwise Kate will contribute 1/3 of the price, but no more than €10 (she's broke :-) and Michael pays the rest.

How much is Michael going to pay? Calculate the amount with two decimals, if necessary.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dee is lazy but she's kind and she likes to eat out at all the nice restaurants and gastropubs in town. To make paying quick and easy she uses a simple mental algorithm she's called The Fair %20 Rule. She's gotten so good she can do this in a few seconds and it always impresses her dates but she's perplexingly still single. Like you probably. 

This is how she does it:

 - She rounds the price `P` at the tens place e.g:
   - 25 becomes 30
   - 24 becomes 20
   - 5 becomes 10
   - 4 becomes 0
 - She figures out the base tip `T` by dropping the singles place digit e.g:
   - when `P = 24` she rounds to 20 drops 0 `T = 2`
   - `P = 115` rounds to 120 drops 0 `T = 12`
   - `P = 25` rounds to 30 drops 0 `T = 3`
   - `P = 5` rounds to 10 drops 0 `T = 1`
   - `P = 4` rounds to 0 `T = 0`
 - She then applies a 3 point satisfaction rating `R` to `T` i.e:
   - When she's satisfied: `R = 1` and she'll add 1 to `T`
   - Unsatisfied: `R = 0` and she'll subtract 1 from `T`
   - Appalled: `R = -1` she'll divide `T` by 2, **rounds down** and subtracts 1
 
## Your Task

Implement a method `calc_tip` that takes two integer arguments for price `p` 

where `1 <= p <= 1000` and a rating `r` which is one of `-1, 0, 1`.

The return value `T` should be a non negative integer.

*Note: each step should be done in the order listed.*

Dee always politely smiles and says "Thank you" on her way out. Dee is nice. Be like Dee.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Ivan had string *s* consisting of small English letters. However, his friend Julia decided to make fun of him and hid the string *s*. Ivan preferred making a new string to finding the old one. 

Ivan knows some information about the string *s*. Namely, he remembers, that string *t**i* occurs in string *s* at least *k**i* times or more, he also remembers exactly *k**i* positions where the string *t**i* occurs in string *s*: these positions are *x**i*,<=1,<=*x**i*,<=2,<=...,<=*x**i*,<=*k**i*. He remembers *n* such strings *t**i*.

You are to reconstruct lexicographically minimal string *s* such that it fits all the information Ivan remembers. Strings *t**i* and string *s* consist of small English letters only.

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

The next *n* lines contain information about the strings. The *i*-th of these lines contains non-empty string *t**i*, then positive integer *k**i*, which equal to the number of times the string *t**i* occurs in string *s*, and then *k**i* distinct positive integers *x**i*,<=1,<=*x**i*,<=2,<=...,<=*x**i*,<=*k**i* in increasing order — positions, in which occurrences of the string *t**i* in the string *s* start. It is guaranteed that the sum of lengths of strings *t**i* doesn't exceed 106, 1<=≤<=*x**i*,<=*j*<=≤<=106, 1<=≤<=*k**i*<=≤<=106, and the sum of all *k**i* doesn't exceed 106. The strings *t**i* can coincide.

It is guaranteed that the input data is not self-contradictory, and thus at least one answer always exists.

Output Specification:
Print lexicographically minimal string that fits all the information Ivan remembers.

Demo Input:
['3\na 4 1 3 5 7\nab 2 1 5\nca 1 4\n', '1\na 1 3\n', '3\nab 1 1\naba 1 3\nab 2 3 5\n']

Demo Output:
['abacaba\n', 'aaa\n', 'ababab\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sasha is taking part in a programming competition. In one of the problems she should check if some rooted trees are isomorphic or not. She has never seen this problem before, but, being an experienced participant, she guessed that she should match trees to some sequences and then compare these sequences instead of trees. Sasha wants to match each tree with a sequence a0, a1, ..., ah, where h is the height of the tree, and ai equals to the number of vertices that are at distance of i edges from root. 

Unfortunately, this time Sasha's intuition was wrong, and there could be several trees matching the same sequence. To show it, you need to write a program that, given the sequence ai, builds two non-isomorphic rooted trees that match that sequence, or determines that there is only one such tree.

Two rooted trees are isomorphic, if you can reenumerate the vertices of the first one in such a way, that the index of the root becomes equal the index of the root of the second tree, and these two trees become equal.

The height of a rooted tree is the maximum number of edges on a path from the root to any other vertex.

Input

The first line contains a single integer h (2 ≤ h ≤ 105) — the height of the tree.

The second line contains h + 1 integers — the sequence a0, a1, ..., ah (1 ≤ ai ≤ 2·105). The sum of all ai does not exceed 2·105. It is guaranteed that there is at least one tree matching this sequence.

Output

If there is only one tree matching this sequence, print "perfect".

Otherwise print "ambiguous" in the first line. In the second and in the third line print descriptions of two trees in the following format: in one line print <image> integers, the k-th of them should be the parent of vertex k or be equal to zero, if the k-th vertex is the root.

These treese should be non-isomorphic and should match the given sequence.

Examples

Input

2
1 1 1


Output

perfect


Input

2
1 2 2


Output

ambiguous
0 1 1 3 3
0 1 1 3 2

Note

The only tree in the first example and the two printed trees from the second example are shown on the picture:

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Petya was late for the lesson too. The teacher gave him an additional task. For some array a Petya should find the number of different ways to select non-empty subset of elements from it in such a way that their product is equal to a square of some integer.

Two ways are considered different if sets of indexes of elements chosen by these ways are different.

Since the answer can be very large, you should find the answer modulo 10^9 + 7.


-----Input-----

First line contains one integer n (1 ≤ n ≤ 10^5) — the number of elements in the array.

Second line contains n integers a_{i} (1 ≤ a_{i} ≤ 70) — the elements of the array.


-----Output-----

Print one integer — the number of different ways to choose some elements so that their product is a square of a certain integer modulo 10^9 + 7.


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

Output
15

Input
4
2 2 2 2

Output
7

Input
5
1 2 4 5 8

Output
7



-----Note-----

In first sample product of elements chosen by any way is 1 and 1 = 1^2. So the answer is 2^4 - 1 = 15.

In second sample there are six different ways to choose elements so that their product is 4, and only one way so that their product is 16. So the answer is 6 + 1 = 7.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp studies at the university in the group which consists of n students (including himself). All they are registrated in the social net "TheContacnt!".

Not all students are equally sociable. About each student you know the value a_{i} — the maximum number of messages which the i-th student is agree to send per day. The student can't send messages to himself. 

In early morning Polycarp knew important news that the programming credit will be tomorrow. For this reason it is necessary to urgently inform all groupmates about this news using private messages. 

Your task is to make a plan of using private messages, so that:

  the student i sends no more than a_{i} messages (for all i from 1 to n);  all students knew the news about the credit (initially only Polycarp knew it);  the student can inform the other student only if he knows it himself. 

Let's consider that all students are numerated by distinct numbers from 1 to n, and Polycarp always has the number 1.

In that task you shouldn't minimize the number of messages, the moment of time, when all knew about credit or some other parameters. Find any way how to use private messages which satisfies requirements above. 


-----Input-----

The first line contains the positive integer n (2 ≤ n ≤ 100) — the number of students. 

The second line contains the sequence a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 100), where a_{i} equals to the maximum number of messages which can the i-th student agree to send. Consider that Polycarp always has the number 1.


-----Output-----

Print -1 to the first line if it is impossible to inform all students about credit. 

Otherwise, in the first line print the integer k — the number of messages which will be sent. In each of the next k lines print two distinct integers f and t, meaning that the student number f sent the message with news to the student number t. All messages should be printed in chronological order. It means that the student, who is sending the message, must already know this news. It is assumed that students can receive repeated messages with news of the credit. 

If there are several answers, it is acceptable to print any of them. 


-----Examples-----
Input
4
1 2 1 0

Output
3
1 2
2 4
2 3

Input
6
2 0 1 3 2 0

Output
6
1 3
3 4
1 2
4 5
5 6
4 6

Input
3
0 2 2

Output
-1



-----Note-----

In the first test Polycarp (the student number 1) can send the message to the student number 2, who after that can send the message to students number 3 and 4. Thus, all students knew about the credit.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Robber Girl likes to scare animals in her zoo for fun. She decided to arrange the animals in a row in the order of non-decreasing height. However, the animals were so scared that they couldn't stay in the right places.

The robber girl was angry at first, but then she decided to arrange the animals herself. She repeatedly names numbers l and r such that r - l + 1 is even. After that animals that occupy positions between l and r inclusively are rearranged as follows: the animal at position l swaps places with the animal at position l + 1, the animal l + 2 swaps with the animal l + 3, ..., finally, the animal at position r - 1 swaps with the animal r.

Help the robber girl to arrange the animals in the order of non-decreasing height. You should name at most 20 000 segments, since otherwise the robber girl will become bored and will start scaring the animals again.

Input

The first line contains a single integer n (1 ≤ n ≤ 100) — number of animals in the robber girl's zoo.

The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 109), where ai is the height of the animal occupying the i-th place.

Output

Print the sequence of operations that will rearrange the animals by non-decreasing height.

The output should contain several lines, i-th of the lines should contain two space-separated integers li and ri (1 ≤ li < ri ≤ n) — descriptions of segments the robber girl should name. The segments should be described in the order the operations are performed.

The number of operations should not exceed 20 000.

If the animals are arranged correctly from the start, you are allowed to output nothing.

Examples

Input

4
2 1 4 3


Output

1 4


Input

7
36 28 57 39 66 69 68


Output

1 4
6 7


Input

5
1 2 1 2 1


Output

2 5
3 4
1 4
1 4

Note

Note that you don't have to minimize the number of operations. Any solution that performs at most 20 000 operations is allowed.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
A newspaper is published in Walrusland. Its heading is `s1` , it consists of lowercase Latin letters. 

Fangy the little walrus wants to buy several such newspapers, cut out their headings, glue them one to another in order to get one big string. 

After that walrus erase several letters from this string in order to get a new word `s2`. 

It is considered that when Fangy erases some letter, there's no whitespace formed instead of the letter. That is, the string remains unbroken and it still only consists of lowercase Latin letters.

For example, the heading is `"abc"`. If we take two such headings and glue them one to the other one, we get `"abcabc"`. If we erase the 1st letter("a") and 5th letter("b"), we get a word `"bcac"`.

Given two string `s1` and `s2`, return the least number of newspaper headings `s1`, which Fangy will need to receive the word `s2`. If it is impossible to get the word `s2` in the above-described manner, return `-1`.

# Example

For `s1="abc", s2="bcac"`, the output should be `2`.

```
"abcabc" --> "bcac"
 x   x
```

For `s1="abc", s2="xyz"`, the output should be `-1`.

It's impossible to get the word `s2`.

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

You are the developer working on a website which features a large counter on its homepage, proudly displaying the number of happy customers who have downloaded your companies software.

You have been tasked with adding an effect to this counter to make it more interesting.  

Instead of just displaying the count value immediatley when the page loads, we want to create the effect of each digit cycling through its preceding numbers before stopping on the actual value.



# Task

As a step towards achieving this; you have decided to create a function that will produce a multi-dimensional array out of the hit count value.  Each inner dimension of the array represents an individual digit in the hit count, and will include all numbers that come before it, going back to 0.

## Rules
* The function will take one argument which will be a four character `string` representing hit count
* The function must return a multi-dimensional array containing four inner arrays
* The final value in each inner array must be the actual value to be displayed
* Values returned in the array must be of the type `number`

**Examples**

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