Có \(n\) học sinh đang đứng xếp hàng trong sân trường, mỗi học sinh có một số thứ tự riêng biệt đánh số từ 1 tới n. Cho biết trạng thái ban đầu của các em học sinh trong hàng, bạn cần thực hiện \(q\) thao tác. Môi thao tác sẽ bao gồm hai chỉ số \(i, j\) chính là số thứ tự của em học sinh và bạn sẽ hoán đổi vị trí của chúng. Bạn hãy in ra thứ tự của hàng sau khi thực hiện xong \(q\) thao tác.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, q \ (1 \leq n, q \leq 2 \times 10^5)\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a[i]\) là số thứ tự các học sinh. Biết rằng \(1 \leq a[i] \leq n\) và không có hai học sinh nào có số thứ tự giống nhau
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(i, j \ (1 \leq i, j \leq n, i \neq j)\) biểu thị một thao tác.

Output

In ra \(n\) số là thứ tự sau cùng của các em học sinh.

Ví dụ

Sample Input

5 2
3 1 2 5 4
1 3
4 5

Sample Output

1 3 2 4 5

H thích ăn bánh cam. Công thức làm bánh gồm 2 lát cam.

H thích ngủ. Vì thế mỗi trái cam luôn được bổ làm 5 (ngũ) miếng. Đây là kỹ thuật độc lạ mà chỉ có H làm được.

Bạn tổ chức một bữa tiệc nhỏ và nhờ H làm bánh. Bạn chuẩn bị \(k\) trái cam.

H có thể làm được tối đa bao nhiêu chiếc bánh?

Input

Gồm một số duy nhất là \(k\) \((k \le 10^8)\).

Output

Đáp án - số chiếc bánh tối đa H có thể làm được.

Ví dụ:

Sample Input 1:

12

Sample Output 1:

30

Sample Input 2:

7

Sample Output 2:

17

Hình chóp đều là hình chóp có mặt đáy là đa giác đều. Hình chóp siêu đều là hình chóp đều có các mặt bên là tam giác đều.

Cho trước ba hình \(H1, H2, H3\) lần lượt là các hình chóp siêu đều có mặt đáy là hình tam giác đều, hình tứ giác đều, hình ngũ giác đều.

H1, H2 và H3

Cho trước ba độ dài \(l1, l2, l3\) lần lượt là độ dài một cạnh của mặt đáy hình \(H1, H2, H3\). Tính tổng thể tích của ba hình \(H1, H2, H3\).

**Input: **

• Ba số nguyên dương \(l1, l2, l3\) không quá \(1000\).

Output: Tổng thể tích của ba hình (làm tròn đến 6 chữ số thập phân).

**Example Input: **

1 1 1

**Example Output: **

0.655056

K là một "tỷ phú đãng trí" anh ta vừa có một chuyến du lịch vòng quanh trái đất. K đã di chuyển sao cho quảng đường đi của mình là ngắn nhất.
Anh ta đã đi qua N nước, mỗi lần đến 1 đất nước nào đó anh ta lại nhớ ra mình cần một bộ quần áo phù hợp để chụp ảnh ở đây.
Vậy là chiếc trực thăng ship đồ lại phải di chuyển từ nhà anh ta cho đến đất nước anh ta đang ở.
Sau khi trở về K muốn biết là chiếc trực thăng của mình đã di chuyển hết bao nhiêu km.
Được biết khoảng cách giữa 2 đất nước liền kề nhau theo cách di chuyển của K. Hãy giúp K tính quãng đường trực thăng di chuyển nhé.

**Input: **

• Dòng đầu gồm 1 số nguyên N là số lượng đất nước K đi qua \(10 \le N \le 50\).
• Dòng tiếp theo gồm N số nguyên là khoảng cách giữa 2 đất nước liền kề (km) \(1000 \le Ai \le 5000\)

Output:

• Quảng đường mà trực thăng đã phải di chuyển (km)

**Example Input: **

10
2046 3550 3652 3234 2367 3063 4429 4315 3949 3671

**Example Output: **

167622

Explanation

Ở ví dụ trên: K đã đi qua 10 nước. Khoảng cách từ điểm xuất phát đến nước thứ 1 là 2046, từ nước thứ nhất cho đến nước thứ 2 là 3550 . . .

Chiếc trực thăng đã phải bay từ nhà cho đến nước thứ nhất rồi trở về, sau đó lại từ nhà đến nước thứ 2 ... ( lưu ý trực thăng sẽ di chuyển từ nhà đến một nước sao cho quảng đường ngắn nhất)