Bạn có một xâu ~A~ và cần thực hiện các bước sau để mã hóa xâu:

• ~Reverse(A)~: đảo ngược các kí tự trong xâu ~A~. Ví dụ ~Reverse("abc") = "cba"~.
• ~Shuffle(A)~: đổi chỗ các kí tự trong xâu ~A~. Ví dụ, ~Shuffle("god")~ có thể là ~"god", "dog", "dgo", ...~
• ~Merge(A,B)~: Trộn hai xâu ~A,B~ với nhau và giữ nguyên thứ tự của các kí tự trong từng xâu. Ví dụ ~Merge("abc","def")~ có thể là ~"abcdef", "adebcf", ...~

Xâu ~A~ (gồm các kí tự Latin in thường) ban đầu đã được mã hóa thành xâu ~S = Merge(Reverse(A),Shuffle(A))~.

Cho xâu ~S~, hãy xác định xâu ~A~ trước khi mã hóa. Do có thể có nhiều kết quả, hãy in ra xâu ~A~ có thứ tự từ điển nhỏ nhất.

Input

• Gồm một dòng chứa xâu ~S~.

Output

• In ra xâu ~A~ thỏa mãn.

Constraints .

• ~|S| \le 10^5~.

Subtask

• Sub ~1~ (~50\%~): ~n \le 1000~.
• Sub ~2~ (~50\%~): ~n \le 10^5~.

Sample Input 1

abbabb

Sample Output 1

abb

~A~ quyết định sẽ đi hái nấm trong rừng.

Có ~m~ con đường một chiều nối giữa ~n~ cây trong khu rừng. Ở mỗi con đường sẽ được trồng một số lượng nấm. Khi ~A~ đi qua một con đường, cậu ấy có thể thu thập tất cả loại nấm trên con đường đó. Khu rừng có một vùng đất màu mỡ kỳ diệu, nơi nấm phát triển với tốc độ chóng mặt. Nấm mới mọc lại ngay sau khi ~A~ hái xong nấm trên một con đường. Cụ thể hơn, sau khi ~A~ đi qua một con đường lần thứ ~i~, sẽ có ~i~ cây nấm mọc ít hơn trước đó có trên đường đi này. Ban đầu, nếu trên đường đi có ~x~ cây nấm, thì ~A~ thu thập được ~x~ cây nấm ở lần đầu tiên, ~x-1~ cây nấm ở lần thứ hai, ~x-1-2~ cây nấm ở lần thứ ba, ... , ~x-1-2-...-i~ cây nấm ở lần thứ ~i~. Tuy nhiên, số lượng cây nấm trên con đường không bao giờ được nhỏ hơn ~0~.

Ví dụ, ban đầu có ~9~ cây nấm trên đường đi. Số lượng cây nấm mà ~A~ có thể thu thập được sau các lần đi qua là ~9, 8, 6, 3~. Ở lần thứ năm ~A~ sẽ không thể thu thập thêm nấm nữa (tuy nhiên vẫn có thể đi qua được con đường này).

~A~ quyết định bắt đầu hành trình của mình ở cây ~s~. Vậy ~A~ có thể thu thập được tối đa bao nhiêu cây nấm?

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n, m~ là số lượng cây nấm và đường đi trong khu rừng.
• ~m~ dòng tiếp theo, mỗi dòng gồm ba số nguyên ~x, y, w~ cho biết đường đi từ ~x~ đến ~y~ ban đầu có ~w~ cây nấm. Có thể tồn tại đường đi từ một cây đến chỉnh nó, hoặc tồn tại nhiều đường đi giữa hai cây.
• Dòng cuối gồm số nguyên dương ~s~ là vị trí xuất phát của ~A~.

Constraints

• ~1 \le n, m \le 10^6~
• ~1 \le x, y \le n~, ~0 \le w \le 10^8~
• ~1 \le s \le n~

Subtasks

• Subtask ~1~ ~(30\%)~: Không có đường đi nào tạo thành chu trình.
• Subtask ~2~ ~(70\%)~: Không có điều kiện gì thêm.

Output

• Gồm một số nguyên duy nhất là lượng cây nấm tối đa mà ~A~ thu thập được

Sample Input 1:

2 2
1 2 4
2 1 4
1

Sample Output 1:

16

Explanation 1:

~A~ lần lượt đi từ ~1...2...1...2~ cho đến khi không còn nấm để thu hoạch. Đáp án là ~4 + 4 + 3 + 3 + 1 + 1 = 16~.

Sample Input 2:

3 3
1 2 4
2 3 3
1 3 8
1

Sample Output 2:

8

Explanation 2:

~A~ có thể đi từ ~1~ đến ~3~ để thu được ~8~ cây nấm.

Cho một đa giác lồi gồm ~n~ đỉnh trên hệ trục tọa độ ~OXY~. Các điểm được đánh số từ ~p_1,p_2,...,p_n~.

Với mỗi điểm ~p_i~ ~(1 \le i \le n)~, hãy xác định chu vi lớn nhất của lục giác gồm các điểm trên đa giác và chứa điểm ~i~.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• ~n~ dòng sau, dòng thứ ~i~ gồm ~2~ số nguyên dương ~x_i,y_i~ miêu tả tọa độ của điểm thứ ~i~. Các điểm được cho theo chiều ngược kim đồng hồ.

Output

• Gồm ~n~ dòng, dòng thứ ~i~ in ra chu vi lớn nhất của lục giác gồm các điểm trên đa giác và chứa điểm ~i~. Kết quả làm tròn đến số thứ ~4~ sau dấu phẩy.

Constraints .

• ~1 \le n \le 1000~.
• ~|x_i|,|y_i| \le 10^9~.

Subtask

• Sub ~1~ (~30\%~): ~n \le 10~.
• Sub ~2~ (~30\%~): ~n \le 100~.
• Sub ~3~ (~40\%~): ~n \le 1000~.

Sample Input 1

8
0 3
1 1
3 0 
6 2
5 5
3 6
1 5
5 0

Sample Output 1

27.3183
26.8052
27.3183
27.3183
27.2445
27.3183
27.3183
27.3183

Đối với một dãy ~b_1,b_2,...,b_m~, một vị trí ~1 \le i < m~ được gọi là "cutable" nếu như tất cả các phần tử trong đoạn ~[b_1,b_2,...,b_i]~ đều bé hơn các phần tử trong đoạn ~[b_{i+1},...,b_m]~.

Cho dãy nguyên dương ~a_1,a_2,...,a_n~ gồm các số nguyên phân biệt trong đoạn ~[1,n]~. Bạn cần trả lời ~q~ truy vấn, mỗi truy vấn gồm hai số nguyên dương ~l,r~. Hãy đếm số vị trí "cutable" đối với dãy ~a_l,a_{l+1},...,a_r~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~ miêu tả hoán vị ~a~.
• Dòng thứ ba chứa số nguyên dương ~q~.
• ~q~ dòng sau, mỗi dòng gồm hai số nguyên dương ~l,r~ ~(1 \le l < r \le n)~ miêu tả truy vấn.

Output

• Với mỗi truy vấn, in ra kết quả tương ứng.

Constraints .

• ~1 \le n,q \le 2*10^5~

Subtask

• Sub ~1~ (~50\%~): ~n,q \le 1000~.
• Sub ~2~ (~50\%~): ~n,q \le 3 \times 10^5~.

Sample Input 1

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

Sample Output 1

1
1
2
0

Cho một đồ thị liên thông vô hướng gồm ~n~ đỉnh, ~n - 1~ cạnh (đây còn được gọi là đồ thị dạng cây). Cạnh thứ ~i~ nối giữa đỉnh ~u_i~ với ~v_i~ và có trọng số là ~w_i~. Quân đưa cho bạn ~m~ tập đỉnh, tập thứ ~i~ gồm ~t_i~ đỉnh là ~a_{i_1}, a_{i_2}, . . . , a_{i_{t_i}}~.

Giả sử ta có hai tập đỉnh ~p~ và ~q~ (một tập không có hai đỉnh giống nhau, nhưng một đỉnh có thể xuất hiện ở cả hai tập).

Đặt ~f(p,q)~ là tổng khoảng cách giữa các cặp đỉnh ~(u, v)~ trong đó ~u~ nằm trong tập ~p~ và ~v~ nằm trong tập ~q~ (khoảng cách giữa hai đỉnh là tổng trọng số các cạnh trên đường đi giữa chúng).

Cụ thể, nếu gọi ~dist(u,v)~ là khoảng cách giữa cặp đỉnh ~(u,v)~ trên cây, ta có tập ~p~ ~=~ ~ \{2,3\}~ và tập ~q~ ~=~ ~\{1,4,3\}~, thì ~f(p,q)~ sẽ được tính như sau:

• ~f(p,q) = dist(2,1) + dist(2,4) + dist(2,3) + dist (3,1) + dist(3,4) + dist(3,3)~.

Quân muốn bạn tính giá trị của biểu thức sau: ~S = \sum_{i=1}^m \sum_{j=i+1}^m f(i,j)~.

Vì kết quả có thể rất lớn, hãy in ra phần dư của ~S~ khi chia cho ~10^9 + 7~.

Dữ liệu vào từ tệp văn bản: tongcay.inp

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ ~(1 \le n,m \le 10^6)~.
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên dương ~u_i,v_i,w_i~ ~(1 \le u_i,v_i \le n; u_i \neq v_i; w_i \le 10^5)~.
• Ở mỗi dòng trong ~m~ dòng cuối cùng, số đầu tiên là ~t_i~, theo sau đó là ~t_i~ số ~a_{i_1},a_{i_2},...,a_{t_i}~ ~(1 \le a_x \le n; a_x \neq a_y \forall x \neq y)~.

Tổng ~t_1 + t_2 + ... + t_m~ không vượt quá ~10^6~.

Kết quả ghi ra tệp văn bản: tongcay.out

• In ra một số nguyên không âm là kết quả bài toán.

Ràng buộc

• Có ~25\%~ số test thỏa mãn: ~n \le 100; m \le 100; t_1 + t_2 + ... + t_m \le 100~.
• Có ~25\%~ số test thỏa mãn: ~n \le 100; m \le 100; t_1 + t_2 + ... + t_m \le 10^5~.
• Có ~20\%~ số test thỏa mãn: ~n \le 10^5; m \le 100; t_1 + t_2 + ... + t_m \le 10^5~.
• Có ~20\%~ số test thỏa mãn: ~n, m, t_1 + t_2 + ... + t_m \le 10^5~.
• ~10\%~ số test còn lại không có ràng buộc gì thêm.

Ví dụ

Input

3 3
1 2 1
2 3 1
1 1
1 2
2 1 3

Output

5

Giải thích

~f(1,2) = dist(1,2) = 1~ ~f(1,3) = dist(1,1) + dist(1,3) = 0 + 2 =2~ ~f(2,3) = dist(2,1) + dist(2,3) = 1 + 1 = 2~

Vậy ~S = 1 + 2 + 2 = 5~