Arrays

ID 38589. practice test

We have a grid with H rows and W columns. The square in the ith row and jth column will be called Square(i, j). Integers from 1 to H·W are written over the entire grid, and an integer written in Square(i, j) is equal to Ai,j.
You are a wizard and can teleport a shape placed on Square(i, j) to Square(x, y) by spending \(|x-i|+|y-j|\) magiks (magic coins).
Now you need to pass Q practice tests on your abilities as a wizard (sorceress). Ith test will be conducted as follows:
- initially the figure is located in the square, where the integer is written Li;
- Let x be the integer written in the square occupied by the shape. Repeatedly move the shape to the square where the integer x+D is written until x will not become equal to Ri. The test ends when x = Ri .
It is guaranteed that Ri- Li is divisible by D.
For each test, find the sum of magics consumed during that test.

Input
The first line contains three integers: H, W and D (\( 1\leq H,W \leq 300\), \(1 \leq D \leq H \cdot W\)).
The following H lines contain W numbers Ai,j (\(1 \leq A_{i,j} \leq H \cdot W\), \(A_{i,j} \ neq A_{x,y} ((i,j) \neq (x,y))\).
The next line contains an integer Q (\(1 \leq Q \leq 10^5\)).
The last Q lines contain 2 integers each: Li and Ri (\(1 \leq L_i \leq R_i \leq H \cdot W\)), \((R_i-L_i)\) multiple of D.

Imprint
For each test, print the sum of magics spent during this test. The output should be in the order of the tests.
 

ID 38716. Gromozeka's Joy

Gromozek has a sequence of integers A of length N. It will make three slices in the  A sequence and split it into four (non-empty) contiguous subsequences B, C, D > and E. He chooses the positions of the slices arbitrarily. Let P, Q, R, S be the sums of elements in B, < code>C, D,  E respectively. Gromozeka will be happy when the absolute difference between the maximum and minimum between P, Q, R, S  minimum. Find the smallest possible absolute difference between the maximum and minimum between P, Q, R, S.

Input
The first line contains an integer N  (\(1<=N<=2 \cdot 10^5\)). The second line contains N integers Ai (\(1<=A_i<=10 ^9\)).

Imprint
Print the smallest possible absolute difference between the maximum and minimum between P, Q, R, S.
 

Examples

ID 38647. Gromozeka's Journey

Gromozeka has the following two personal principles: he never travels more than L in one day. He never sleeps outdoors. That is, he must be at the hotel at the end of the day.
The Planet Blue has N hotels and all are located on the same street. The coordinate of the ith hotel (1<=i<=N) is xi.
Traveling around the planet Bluk, Gromozeka planned Q moves. With each move he plans to change hotel aj to bj (1<=j<= Q). For each move, find the minimum number of days Gromozeka needs to get from the ajth hotel to the bjth, following his principles.
It is guaranteed that he can always travel from the ajth hotel to the bjth th hotel.< br />
Input
The first line contains an integer N (2<=N<=10⁵) - the number of hotels on the planet Bluk. The second line contains N numbers xi - coordinates of the i-th hotel (1<=x₁<x<sub>2< /sub><...<xN<=10⁹ , xi+1−x i<=L). The third line contains the number L (1<=L<=10⁹).  The fourth line contains the number Q (1<=N<=10⁵). 
The last Q lines contain two different numbers aj and bj (1<=aj,bj<=N). All numbers are integers.

Imprint
Print Q lines. The j-th line (1<=j<=Q) should contain the minimum number of days Gromozeka needs to get from  aj-th hotel to bj-th hotel.</sub>

Examples

ID 38926. Snezhik Sugrobovich - 2

In some world, it's December 31st and all the fun is just beginning. Snezhik Sugrobovich made N large snowballs and arranged them in a row from left to right. On each ith snowball, counting from the left (1 <= i <= N ), he wrote the integer ai. He invites you to play a game. Snezhik Sugrobovich allowed to break no more than N − 1 snowballs of your choice. 

Let's say there are K snowballs left. Snezhik Sugrobovich will be satisfied and give you a good gift if for each integer i (1<=i<=K) on the i-th snowball, counting the remaining snowballs on the left , an integer will be written i.
Find the minimum number of snowballs you need to break in order to receive a gift. If it doesn't work, then print -1.

Input
In the first line, the program receives an integer N (1 <= N <= 200000) as input. In the second line - N natural numbers ai (1<=ai<=N). 

Imprint
Print the minimum number of snowballs that need to be broken to get a present, or print -1 if it's impossible.
 

Examples

ID 33200. Vector: Beginning

ID 30686. Vector sort: Start

ID 42324. Find and count

Given two integer sequences, each of length N: A = (A1, A 2, ..., AN) and B = (B1, B2, ..., BN).
All A elements are different. All B elements are also different.

Print the following two values.

1. The number of integers contained in both A and B appearing in the same position in the two sequences. In other words, the number of integers  i numbers such that Ai = Bi.
2. The number of integers contained in both A and B that appear at different positions in the two sequences. In other words, the number of pairs of integers  (i, j) numbers such that Ai = Bj and i ≠ j.

Examples

4
1 3 5 2
2 3 1 4

1
2

3
1 2 3
4 5 6

0
0

ID 38463. peaceful rooks

On a chessboard of N x times; There are N rooks in chess that do not attack each other, that is, there is exactly one rook on each vertical and each horizontal.


The chessboard is rotated 90° clockwise. Output the resulting set-up of rooks.


Input
The first line of the input contains an integer N, 1 ≤ N≤ 10⁵ — board size. The next N lines contain one number each from 1 to N, namely, the i-th line contains the number a_i — number of the column in which the rook stands on the i-th column. In this problem, the horizontals are numbered from 1 to N from top to bottom, the verticals are numbered from 1 to N from left to right (see figure).

Imprint
The program should output N numbers — the placement of the rooks after the turn in the same format.

Examples