Finding a Home

Interview

Time limit1sMemory limit1024 MB

Summary

For each query L R, people L to R may swap houses among themselves. Print the sequence that maximizes the sum of house index times person number.

Level: Easy3 of 10
Topics: Greedy, Sorting, Implementation
Solved: No attempts yet

Problem

Seogang University has $N$ empty houses. The university wants to assign $N$ people so that each person moves into exactly one house. For each person $y$ who moves into house $x$ , the university reduces their tax by $xy$ .

The assignment is given as a sequence $A_1, A_2, \dots, A_N$ of integers from $1$ to $N$ , where each value appears once. This means house $i$ is assigned to person $A_i$ .

Write a program that solves the following query.

$L$ $R$ : Starting from the initial assignment, the people numbered $L$ through $R$ may swap the houses currently assigned to them with each other as many times as the university wants. After reassigning, the total tax reduction is maximized. Output the sequence $A$ .

Every query is independent. After each query, the sequence $A$ returns to its initial state.

Input

The first line contains the length $N$ of the sequence. $(1 \le N \le 300)$

The second line contains the sequence $A_1, A_2, \dots, A_N$ , separated by spaces. $(1 \le A_i \le N)$

The third line contains the number of queries $M$ . $(1 \le M \le 300)$

The next $M$ lines each contain two integers $L$ and $R$ , separated by a space. $(1 \le L \le R \le N)$

Output

For each query, print the answer on its own line.

Each line contains the sequence $A_1, A_2, \dots, A_N$ after the query is finished, separated by spaces.

If there are several valid answers, print any one of them.

Examples1

Example 1

Input

Expected output

1 2 4 3 5
1 3 4 2 5
1 2 3 4 5