Cho một đồ thị ~n~ đỉnh và không có cạnh. Có ~q~ truy vấn thuộc một trong hai loại sau:

• 1 u v thêm cạnh giữa ~u~ và ~v~.
• 2 u v kiểm tra liệu ~u~ và ~v~ có được kết nối với nhau không.

Input

• Dòng đầu tiên gồm hai số nguyên ~n,q~.
• ~q~ dòng tiếp theo, mỗi dòng gồm 3 số nguyên ~t, u, v~, một truy vấn.

Output

• Với mỗi truy vấn loại 2, in ra YES nếu ~u~ và ~v~ kết nối với nhau, ngược lại in ra NO.

Điều kiện

• ~1 \le n, q \le 10^5~.
• ~1 \le u, v \le n~.

Ví dụ

Input:

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

Output:

YES
NO

Cho một đồ thị ~n~ đỉnh và không có cạnh. Có ~q~ truy vấn thuộc một trong hai loại sau:

• 1 u v thêm cạnh giữa ~u~ và ~v~.
• 2 u tính tổng các đỉnh trong thành phần liên thông của ~u~.

Input

• Dòng đầu tiên gồm số nguyên ~n~.
• ~q~ dòng tiếp theo, mỗi dòng là một truy vấn. Nếu là truy vấn loại 1, một dòng gồm 3 số nguyên ~1, u, v~. Nếu là truy vấn loại 2, một dòng gồm 2 số nguyên ~2, u~.

Output

• Với mỗi truy vấn loại ~2~, in ra một số nguyên trên một dòng là tổng các đỉnh trong thành phần liên thông của ~u~.

Điều kiện

• ~1 \le n, q \le 10^5~.
• ~1 \le u, v \le n~.

Ví dụ

Input:

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

Output:

6
4

Cho một đồ thị liên thông, vô hướng và có trọng số gồm ~n~ đỉnh và ~m~ cạnh. Tìm trọng số của cây khung nhỏ nhất của đồ thị.

Cây khung là một tập hợp các cạnh của đồ thị, không chứa chu trình và kết nối tất cả các đỉnh của đồ thị. Trong đồ thị có trọng số, cây khung nhỏ nhất là cây khung có tổng trọng số các cạnh nhỏ nhất

Input

• Dòng đầu tiên gồm 2 số nguyên ~n, m~.
• ~m~ dòng tiếp theo gồm 3 số nguyên ~u, v, w~, có cạnh trọng số ~w~ giữa ~u~ và ~v~.

Output

• In ra trọng số của cây khung nhỏ nhất.

Điều kiện

• ~1 \le n, m\le 10^5~.
• ~1 \le u, v \le n~.
• ~1 \le w \le 10^9~.

Ví dụ

Input:

3 3
1 2 1
2 3 2
3 1 3

Output:

3

Gọi ~A~ là dãy số với ~A(i)~ được tạo bởi ghép ~i~ số nguyên tố đầu tiên với nhau: ~2, 23, 235, 2357, 235711, 23571113, ... ~.

Cho ~n~ và ~k~, hãy tìm cách xóa ~k~ chữ số ra khỏi số ~A(n)~ để thu được số lớn nhất có thể.

Input

• Gồm một dòng chứa hai số nguyên không âm ~n~ và ~k~ ~(1 \le n \le 50000)~, dữ liệu đảm bảo ~k~ bé hơn số chữ số của ~A(n)~.

  Output

• In ra một dòng miêu tả kết quả của bài toán.

Subtask

• ~50\%~ số test có ~n \le 50~.
• ~50\%~ số test không ràng buộc gì thêm.

Sample Input 1:

7 4

Sample Output 1:

711317

Cho một xâu ~S~, hãy loại bỏ tất cả các kí tự thừa sao cho với mỗi chữ cái chỉ xuất hiện một lần duy nhất. Vì có nhiều cách loại bỏ nên bạn hãy đưa ra xâu có thứ tự từ điển nhỏ nhất.

Input

• Gồm một dòng duy nhất có xâu ~S~ (~1 \le |S| \le 10^4~)

Output

• In ra xâu ~S~ sau khi đã được loại bỏ các kí tự thừa có thứ tự từ điển nhỏ nhất.

Sample Input 1

bcabc

Sample Output 1

abc

Sample Input 2

cbacdcbc

Sample Output 2

acdb

Notes

Ở test ví dụ thứ nhất, các xâu thỏa mãn có thể là bca, cab, bac, abc. Tuy nhiên, ta chỉ chọn xâu có thứ tự từ điển nhỏ nhất là xâu abc

Cho một dãy số ~a_1, a_2, ... a_N~. Một nghịch thế là một cặp số ~u, v~ sao cho ~u < v~ và ~a_u > a_v~. Nhiệm vụ của bạn là đếm số nghịch thế.

Input

• Dòng đầu ghi số nguyên dương ~N~ ~(N \leq 10^5)~.
• Dòng sau gồm ~N~ số nguyên dương ~a_i~ ~( 1 ≤ a_i ≤ 10^5 )~.

Output

• In ra kết quả của bài toán.

Subtasks

• Subtask 1: ~n \leq 5000~. (50%)
• Subtask 2: Không giới hạn gì thêm.

Sample Input 1

3
3 1 2

Sample Output 1

2

Cho một dãy số gồm ~n~ phần tử ~a_1~, ~a_2~, ..., ~a_n~. Với một dãy số gồm ~m~ phần tử ~b_1~, ~b_2~, ..., ~b_m~, trọng số của dãy ~b~ được định nghĩa là tích của giá trị lớn nhất và nhỏ nhất của dãy. Hãy tìm tổng trọng số của các dãy con của dãy ~a~.

Dãy con của dãy ~a~ được định nghĩa là một tập ~a_{i_1}~, ~a_{i_2}~, ..., ~a_{i_k}~ với 1 ~\le~ ~i_1~ < ~i_2~ < ... < ~i_k~ ~\le~ ~n~.

INPUT

• Dòng đầu chứa số nguyên dương ~n~ (~1~ ~\le~ ~n~ ~\le~ ~10^5~).
• Dòng thứ hai chứ ~n~ số nguyên không âm ~a_i~ (~0~ ~\le~ ~a_i~ ~\le~ ~10^9~).

OUTPUT

• In ra một số nguyên duy nhất là tổng trọng số của tất cả các dãy con. Do output có thể rất lớn nên hãy in ra kết quả mod ~10^9 + 7~.

SAMPLE TEST

Input:

5
4 2 1 3 4

Output:

208

SUBTASKS

• ~30\%~ số điểm có ~n~ ~\le~ ~20~.
• ~30\%~ số điểm có ~n~ ~\le~ ~10^3~.
• ~40\%~ số điểm còn lại có ~n~ ~\le~ ~10^5~.

Đây là bài toán giao tiếp với máy chấm (Interactive problem)

Jury có một con số ~n~ bí mật. Điều duy nhất bạn biết về con số này là ~1 \leq n \leq 2 \times 10^9~. Jury và bạn sẽ chơi một trò chơi như sau: Bạn sẽ được chọn một số bất kỳ và nói cho [Jury nghe số đó. Jury sẽ cho bạn biết con số của bạn lớn hơn, nhỏ hơn, hay bằng ~n~. Hãy đoán xem ~n~ là số nào trong không quá ~31~ câu hỏi.

Cách Thức Giao Tiếp

Mỗi lượt, bạn sẽ in ra một số ~x~ trên một dòng (~1\leq x \leq 2 \times 10^9~). Máy tính sẽ đọc ~x~ và in ra màn hình một chuỗi tương ứng với các trường hợp sau:

• "BIGGER" nếu ~n > x~
• "SMALLER" nếu ~n < x~
• "HOLA" nếu ~n = x~.

Lưu ý:

• Chuỗi mà máy in ra màn hình không có dấu "
• Nếu các bạn in ra một output không hợp lệ (không phải là một số, số ngoài đoạn ~[1, 2 \times 10^9]~ thì nhiều khả năng bị TLE.
• Sau khi in mỗi số, bạn phải xuống dòng (ví dụ in endl trong C++)
• Khi in ra một dòng, các bạn phải flush output bằng cách cout.flush hoặc dùng endl thay vì \n

Example

Con số bí mật trong test này là 5.

Hôm nay lớp Cam có một trò chơi trong giờ Toán. Cô giáo nghĩ trong đầu một số nguyên ~X~ trong khoảng ~1~ đến ~10^6~. Các bạn học sinh cần tìm được số bí mật X với ít nhất các câu hỏi có dạng: "Ước chung lớn nhất của một số ~X~ với một số ~Y~ là bao nhiêu?". Bạn nào dùng càng ít câu hỏi thì điểm càng cao.

Các bạn hãy giúp cam viết một chương trình, sử dụng các câu lệnh được cung cấp để tìm ra số bí mật ~X~ mà hết ít câu hỏi nhất.

Interaction

• Để tương tác với máy chấm, hãy in mỗi lệnh trên từng dòng. Câu trả lời sẽ được máy chấm in ra trên một dòng khác, và bạn đọc vào. Lưu ý flush luồng ra chuẩn sau mỗi dòng được in ra bằng lệnh fflush(stdout) hoặc cout << endl;

• Các câu lệnh:

  • ucln Y (~Y~ là một số nguyên dương bất kì ~1 \le Y \le 10^{18}~): máy sẽ in ra ước chung lớn nhất của X và Y.
  • traloi x (~x~ là một số nguyên dương): là số bí mật ~X~ mà bạn đã xác định được. Chương trình bắt buộc phải in ra traloi một lần duy nhất, nếu không sẽ bị ~0~ điểm. Thủ tục này khi được gọi sẽ tự động thoát chương trình bằng câu lệnh exit.

Scoring

• Với mỗi test, nếu chương trình của bạn trả lời với đáp án không chính xác, chạy quá thời gian quy định, sử dụng quá ~1000000~ câu hỏi hoặc gặp các lỗi dẫn tới dừng chương trình, bài làm sẽ nhận 0 điểm cho test đó. Số điểm cho mỗi test sẽ giảm dần khi số câu hỏi bạn sử dụng tăng lên.

Example

• Giả sử số bí mật ~X~ cần tìm là ~300000~, quá trình nhập xuất có thể diễn ra như sau:

  ```
  >> ucln 100000
  << 100000
  >> ucln 200000
  << 100000
  >> ucln 500000
  << 100000
  >> ucln 900000
  << 300000
  >> traloi 300000
  ```