Độ khó: Khó (4/4 điểm)

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Một công ty có ~N~ phòng, kết nối với nhau bằng ~N - 1~ hành lang nội bộ có thể di chuyển theo hai chiều sao cho một hành lang nối trực tiếp hai phòng và giữa hai phòng bất kỳ luôn có đường đi đến nhau.

Công ty có ~M~ nhân viên, ban đầu mỗi nhân viên làm việc tại một phòng nhất định. Một phòng có thể có nhiều nhân viên. Phòng, hành lang và nhân viên đều được đánh chỉ số bằng các số nguyên liên tiếp nhau, bắt đầu từ ~1~.

Mỗi nhân viên có một chỉ số hiệu suất cá nhân, ban đầu bằng ~0~.

Khi phòng ~X~ được bổ sung tiện ích, hiệu suất của tất cả nhân viên hiện đang làm việc tại phòng ~X~ tăng thêm ~V~ đơn vị.

Khi một nhân viên bị điều chuyển từ phòng ~A~ qua phòng ~B~, hiệu suất của nhân viên đó giảm đi ~K~ đơn vị, với ~K~ là độ dài quãng đường ngắn nhất từ phòng ~A~ đến phòng ~B~ (tính bằng số hành lang).

Hãy cho biết hiệu suất làm việc của một nhân viên trong quá trình công ty thực hiện việc trang bị tiện ích cho các phòng và điều chuyển nhân viên giữa các phòng.

Input

Vào từ file văn bản HSNV.INP:

• Dòng đầu gồm ba số nguyên ~N, M, Q~ (~2 \le N \le 2 \cdot 10^5~, ~1 \le M, Q \le 2 \cdot 10^5~) lần lượt là số phòng, số nhân viên, số yêu cầu.
• Dòng thứ hai gồm ~M~ số nguyên ~a_1, a_2, \ldots, a_M~, trong đó ~a_i~ là phòng mà nhân viên ~i~ ban đầu làm việc (~1 \le a_i \le N~).
• ~N - 1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u, v~ (~1 \le u, v \le N, u \ne v~), cho biết có một hành lang nối trực tiếp giữa phòng ~u~ và phòng ~v~.
• ~Q~ dòng tiếp theo mô tả các yêu cầu, thuộc một trong ba dạng sau:
  • e X V: phòng ~X~ được bổ sung tiện ích, tăng thêm ~V~ đơn vị hiệu suất cho tất cả nhân viên hiện đang làm việc tại phòng đó (~1 \le X \le N, 0 \le V \le 10^9~).
  • t L R Z: tất cả nhân viên có chỉ số từ ~L~ đến ~R~ đồng loạt được chuyển về phòng ~Z~ (~1 \le L \le R \le M, 1 \le Z \le N~).
  • q K: truy vấn hiệu suất hiện tại của nhân viên ~K~ (~1 \le K \le M~).

Đảm bảo có ít nhất một yêu cầu dạng q.

Output

Ghi ra file văn bản HSNV.OUT:

• Với mỗi yêu cầu dạng q K, in ra một số nguyên trên một dòng là hiệu suất hiện tại của nhân viên ~K~.

Scoring

Sample Input 1

3 2 5
1 2
1 2
2 3
q 1
e 2 5
q 2
t 1 1 3
q 1

Sample Output 1

0
5
-2

Độ khó: Khá (3/4 điểm)

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Bạn Minh được cho trước một dãy số nguyên dương gồm ~N~ phần tử ~a_1, a_2, \ldots, a_N~. Bạn cần thực hiện ~Q~ truy vấn, trong đó mỗi truy vấn ứng với một đoạn con ~[L, R]~ của dãy trên với ~1 \le L \le R \le N~ và cần tính tổng của tất cả các giá trị ~a_i \% a_j~ (~a_i~ chia lấy phần dư cho ~a_j~) với mọi cặp chỉ số ~(i, j)~ thỏa mãn ~L \le i, j \le R~.

Yêu cầu: Hãy viết chương trình giúp Minh trả lời các truy vấn đó.

Input

Dữ liệu vào từ file THAOTAC.INP:

• Dòng đầu tiên chứa hai số nguyên ~N, Q~ cho biết số phần tử trong dãy và số lượng truy vấn.
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, \ldots, a_N~.
• Trong ~Q~ dòng tiếp theo, mỗi dòng là một cặp số nguyên ~L, R~ (~1 \le L \le R \le N~).

Output

Ghi ra file THAOTAC.OUT gồm ~Q~ số trên các dòng khác nhau, mỗi dòng là câu trả lời các truy vấn đã cho theo thứ tự.

Scoring

Sample Input 1

3 2
1 2 4
1 3
2 2

Sample Output 1

4
0

Độ khó: Khá (3/4 điểm)

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Trong một bảo tàng lịch sử nổi tiếng, người quản lí đang được giao nhiệm vụ bảo quản một bản đồ cổ vốn đã trải qua hàng trăm năm. Theo thời gian, để tiện lưu trữ, bản đồ đã được gấp lại nhiều lần tại những nếp gấp khác nhau. Bản đồ có ~N + 1~ nếp gấp cách đều nhau được đánh số từ ~0~ đến ~N~ từ mép trái qua mép phải. Mỗi lần gấp tại nếp gấp vị trí ~X~, phần bản đồ ngắn hơn sẽ được gấp chồng lên phần còn lại. Trường hợp hai phần bằng nhau thì gấp phần bản đồ bên trái lên phần bên phải. Sau ~K~ lần gấp như thế, tại cùng một vị trí có thể có nhiều nếp gấp. Giả sử độ dày của bản đồ sau các lần gấp tăng không đáng kể.

Một ngày nọ, khi bảo tàng tổ chức triển lãm tấm bản đồ cổ, ông quản lí đặt tấm bản đồ đã được gấp trên mặt bàn để kiểm tra. Sau khi quan sát, ông muốn biết số nếp gấp chồng lên nhau tại những vị trí nếp gấp tiếp xúc với mặt bàn.

Yêu cầu: Hãy viết chương trình giúp người quản lí trả lời câu hỏi trên.

Input

Vào từ file BANDO.INP:

• Dòng 1: 2 số nguyên ~N~ và ~K~.
• Dòng 2: ~K~ số nguyên là các vị trí nếp gấp (~0 \le x_i < N + 1~ với ~i = 1, 2, 3, \ldots, K~).

Output

Ghi ra file BANDO.OUT:

• Dòng 1: Số lượng vị trí nếp gấp tiếp xúc với mặt bàn.
• Dòng 2: Số lượng nếp gấp tại vị trí đó theo thứ tự từ trái sang phải.

Scoring

Sample Input 1

7 2
3 2

Sample Output 1

4
2 3 2 1

Notes

Minh hoạ cho test 1.