Contest #04/2022

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 số \(i, j\) chính là số thứ tự của hai học sinh và bạn sẽ hoán đổi vị trí của họ. 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ị thao tác hoán đổi vị trí của học sinh mang số \(i\) và học sinh mang số \(j\).

Output

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

Example

5 2
3 1 2 5 4
1 3
4 5

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.

Example

12

30

7

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.

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

1 1 1

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 A_i \le 5000\)).

Output

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

Example

10
2046 3550 3652 3234 2367 3063 4429 4315 3949 3671 

167622