Cho một dãy gồm N phần tử ~a_1~, ~a_2~, ~a_3~ ,.., ~a_n~. Hãy đếm số lượng phần tử khác nhau trong dãy.

Input

• Dòng đầu tiên gồm một số nguyên N ~(1 \leq N \leq 10^5)~ là số lượng phần tử của dãy.
• Dòng thứ hai chứa n số lần lượt là phần tử trong mảng a : ~a_1, a_2, a_3, ... , a_n (1 \leq a_i \leq 10^5)~.

Output

In ra màn hình số lượng phần tử khác nhau.

Sample Input 1

5
3 1 3 2 4

Sample Output 1

4

Giải thích

• Test 1 : Dãy có 4 giá trị phân biệt là {1,2,3,4}

Nguồn: https://cses.fi/problemset/task/1137

Cho một cây gồm n đỉnh và n - 1 cạnh, các đỉnh được đánh số từ 1 đến n và gốc của cây là 1. Mỗi đỉnh có một giá trị.

Nhiệm vụ của bạn là thực hiện các truy vấn có dạng sau.

1. Thay đổi giá trị của đỉnh s thành x.
2. Tính tổng giá trị các đỉnh con của s.

Input

• Dòng đầu tiên chứa 2 số nguyên n và q ~(1 \leq n, q \leq 2.10^5)~: số lượng đỉnh và số lượng truy vấn.
• Dòng tiếp theo có n số nguyên ~v_1~, ~v_2~, ..., ~v_n~ ~(1 \leq v_i \leq n)~ : giá trị của từng đỉnh.
• n - 1 dòng tiếp theo, mỗi dòng chứa 2 số nguyên a ,b ~(1 \leq a, b \leq n)~ chỉ định 1 cạnh của cây giữa đỉnh a và đỉnh b.
• q dòng tiếp theo mỗi dòng sẽ thuộc một trong 2 dạng "1 s x" hoặc "2 s". ~(1 \leq s \leq n)~ ~(1 \leq x \leq 10^9)~

Output

• In ra kết quả với mỗi truy vấn loại 2.

Sample Input 1

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

Sample Output 1

8
10

Nguồn đề: thầy Nguyễn Thanh Tùng

Lực lượng Mũ nồi xanh giữ gìn hòa bình của Liên Hiệp Quốc có những chương trình huấn luyện đặc biệt. Ví dụ tổ 3 người đã ở vị trí tọa độ (0, 0) trong thời gian nguyên ngắn nhất phải tỏa ra khống chế một vùng tam giác có diện tích không nhỏ hơn s/2 với đỉnh là vị trí của 3 người. Ở mỗi đơn vị thời gian chỉ có một người được di chuyển, hai người còn lại ở nguyên vị trí hiện tại của mình làm nhiệm vụ yểm trợ. Mỗi lần di chuyển một người đi được một quãng đường độ dài bằng 1 theo hướng tùy chọn Đông, Tây, Nam hay Bắc.

Hãy xác định thời gian tối thiểu cần thiết để thực hiện bài huấn luyện.

Input

• Gồm một dòng chứa số chuyên s ~(0 \leq s \leq 10^{18} )~.

Output

• In ra màn hình thời gian tối thiểu tính được.

Sample Input 1

3

Sample Output 1

4

Nguồn đề: thầy Nguyễn Thanh Tùng

Các nhà bác học thế giới dự định tạo một ngân hàng gien tất cả các động thực vật nằm trong danh sách đỏ. Tòa nhà lưu trữ gien phải được bảo vệ kép ở dạng hai phòng lồng vào nhau.

Hiện tại đang có máy in 3D cho phép in n loại phòng hình chữ nhật, loại thứ i có cạnh chạy từ tây sang đông có độ dài ~a_i~, cạnh kia có độ dài ~b_i~ chạy từ bắc xuống nam và không đổi hướng khi in.

Căn phòng kích thước ~a_i~ x ~b_i~ lồng được vào trong phòng kích thước ~a_j~ x ~b_j~ nếu ~a_i \leq a_j~ và ~b_i \leq b_j~. Để nâng cao hệ số bảo vệ phòng trong và phòng ngoài phải thuộc hai loại khác nhau.

Người ta được phép xây dựng phòng trong theo kiểu tùy chọn trong số n loại đã có. Nếu chọn loại phòng trong có kích thước ~a_i~ x ~b_i~ thì có thể chọn phòng ngoài loại ~a_j~ x ~b_j~ nào đó, mở rộng kích thước thành ~a~x~b~ để thỏa mãn điều kiện ~a \ge a_i~, ~b \ge b_i~. Nhưng như vậy phải viết thêm chương trình mới và cải tiến thiết bị in với chi phí là (a+b) - ~(a_j + b_j)~.

Chi phí cho dự án có hạn nên Hội đồng khoa học quyết định trước hết khảo sát, nếu chọn phòng trong là loại i với i = 1, 2, .. ,n thì chi phí bổ sung tối thiểu để có phòng ngoài thích hợp là bao nhiêu.

Hãy xác định chi phí bổ sung tối thiết cần thiết cho mỗi loại phòng trong với các mẫu hiện có.

Input

• Dòng đầu tiên chứa số nguyên n ~(2 \leq n \leq 10^{5} )~.
• Dòng thứ i trong n dòng tiếp theo chứa 2 số nguyên ~a_i~ và ~b_i~, ghi cách nhau một dấu cách ~( 1 \leq a_i, b_i \leq 10^9)~.

Output

• In ra một dòng gồm n số nguyên, số thứ i ứng với chi phí bổ sung tối thiểu nếu chọn phòng trong loại i, i = 1, 2, 3, .., n. Các số ghi cách nhau một dấu cách.

Sample Input 1

5
4 4
6 3
2 5
7 2
1 10

Sample Output 1

1 1 1 1 5

Nguồn đề: thầy Nguyễn Thanh Tùng

Trong đội hình thi đấu bóng đá, cặp tiền vệ trung tâm đóng vai trò hết sức quan trọng: làm nhiệm vụ thu hồi bóng trả cho hàng hậu vệ hoặc chuyền cho hàng tiền đạo phát động tấn công.

Để chuẩn bị cho một trận đấu hết sức quan trọng, huấn luyện viên cho các tiền vệ tập phối hợp xử lí n tình huống có thể xuất hiện, kỹ năng xử lý tình huống i mang lại hiệu quả ~h_i~, i = 1, 2, .., n và hiệu quả của hàng tiền vệ là ~\sum_{i=1}^n h_i~. Để đảm bảo bí mật nhằm mang lại bất ngờ cho đối phương huấn luyện viên đã thay các chữ số (trong hệ thập phân), mỗi chữ số bằng chữ số khác (có thể giống như cũ), đảm bảo vẫn không làm xuất hiện các chữ số 0 không có ý nghĩa. Việc thay thế được thực hiện bằng cách hoán vị các chữ số từ 0 đến 9 và mỗi chữ số d trong ~h_i~ được thay bằng vị trí số ở vị trí d trong hoán vị. Các vị trí trong hoán vị được đánh số bắt đầu từ 0. Ví dụ, với hoán vị (3, 6, 0, 7, 8, 5 ,9 ,1 ,2 ,4) số 985 trở thành 645. Kết quả thay thế từ ~h_i~ có được giá trị ~a_i~ - số mà huấn luyện viên công bố ở buổi họp báo trước trận đấu.

Trợ lý huấn luyện viên của đội đối thủ hiểu rằng số đã được mã hóa và cách mà huấn luyện viên của đội đó thường dùng để mã hóa. Ông cố gắng tính nhanh hiệu quả tối đa có thể có để hiệu quả của hàng tiền vệ đội bạn, tức là giá trị lớn nhất của ~\sum_{i=1}^n h_i~.

Từ các số ~a_1~, ~a_2~, , ~a_3~, ... , ~a_n~ hãy xác định giá trị lớn nhất của ~\sum_{i=1}^n h_i~.

Input

• Dòng đầu tiên chứa một số nguyên n ~( 1 \leq n \leq 10^5 )~
• Dòng thứ 2 chứa n số nguyên ~a_1~, ~a_2~, , ~a_3~, ... , ~a_n~ ~(1 \leq a_i \leq 10^9)~ các số ghi cách nhau một dấu cách.

Output

• Đưa ra một số nguyên - hiệu quả lớn nhất có thể đạt.

Sample Input 1

4
1234 123 12 1

Sample Output 1

10970

Nguồn đề: thầy Nguyễn Thanh Tùng

Hai thành phố Alpha và Betta vốn là hai trung tâm thương mại lớn. Trong một thời gian dài chỉ số hấp dẫn thu hút đầu tư của hai thành phố là như nhau và bằng giá trị nguyên dương x.

Dần dần, do nhiều lí do khác nhau, Alpha càng ngày càng trở nên hấp dẫn hơn và các nhà đầu tư bắt đầu chuyển vốn đầu tư từ Betta sang Alpha.

Một công trình khảo sát khẳng định trong n năm kể từ khi bắt đầu xảy ra khác biệt, năm thứ i chỉ số hấp dẫn của Alpha tăng thêm một giá trị nguyên ~a_i \ge 1~, trong khi đó chỉ số hấp dẫn của Betta giảm ~a_i~, i = 1, 2, .. n. Kết luận này gây ra nhiều tranh cãi trong xã hội.

Hãy dựa vào chỉ số năm n đã trôi qua kể từ khi có sự khác biệt chỉ số và chỉ số hấp dẫn hiện tại a, b của hai thành phố Alpha, Betta, hãy xác định có thể tồn tại khả năng thay đổi theo quy luật đã nêu hay không.

Input

• Một dòng gồm 3 số nguyên a, b và n ~(0 \leq a, b, n \leq 10^9)~

Output

• In ra màn hình "YES" hoặc "NO" (không có ngoặc kép) phụ thuộc vào kết quả kiểm tra.

Sample Input 1

7 1 2

Sample Output 1

YES