Bé Tommy rất thích tìm hiểu về các số đặc biệt, hôm trước trong giờ học lập trình thầy giáo dạy cho bé về số hoàn hảo (số hoàn hảo là số có tổng các ước (không kể nó) bằng chính nó, ví dụ số ~6~ là số hoàn hảo vì ~6=1+2+3~), bé cảm thấy hứng thú với con số này. Về nhà bé nghĩ ra khá nhiều bài toán xử lí số hoàn hảo. Nhưng hôm nay, thầy cho bé một bài tập rất hóc búa, nghĩ mãi không ra cách làm tốt nhất để được tối đa điểm của bài, nên bé nhờ các bạn học sinh giỏi làm giúp. Bài toán như sau:

Cho dãy ~a_1,a_2,…,a_n~ , ban đầu tất cả các phần tử có giá trị bằng ~0~. Có ~m~ phép biến đổi dạng ~(u,v,k)~: tăng giá trị các phần tử từ vị trí ~u~ đến vị trí ~v~ lên ~k~ đơn vị. Dữ liệu đảm bảo sau ~m~ phép biến đổi ~0<a_i \le 10^6~ ~(\forall i=1..n)~ và có ít nhất một số hoàn hảo trong dãy. </p>

Yêu cầu:

• Với dãy ~a_1,a_2,…,a_n~ sau ~m~ phép biến đổi, thầy yêu cầu đưa ra vị trí các số hoàn hảo theo thứ tự tăng dần.

Input

• Dòng đầu là hai số nguyên dương ~n,m~ tương ứng là số phần tử của dãy và số lượng phép biến đổi;
• ~m~ dòng sau mỗi dòng là ba số nguyên dương ~u,v,k~ ~(0 < u \le v \le n)~.

Output

• In ra các dòng, mỗi dòng chứa một số nguyên dương là vị trí của số hoàn hảo tìm được trong dãy theo thứ tự tăng dần.

Subtask

• Subtask ~1~ (~35\%~ số điểm): ~ 1 \le n,m \le 10^2~
• Subtask ~2~ (~35\%~ số điểm): ~n \le 10^5, m \le 10^3~
• Subtask ~3~ (~30\%~ số điểm): ~n \le 10^5, m \le 10^5~

Sample Input 1

6 3
1 6 6
2 3 4
3 5 22

Sample Output

1
4
5
6

Explanation 1

• Dãy thu được sau ~3~ phép biến đổi là: 6 10 32 28 28 6

Vùng đất Midland đang có chiến tranh tàn khốc. Bạn đang ở vùng giao tranh, và giờ phải gửi tài liệu mật từ đơn vì tới cho sở chỉ huy. Vùng này được biểu diễn dưới dạng một ma trận ~n \times m~, ô ở hàng ~i~ cột ~j~ được gọi là ô ~(i,j)~.

Đây là tài liệu mật và khẩn cấp, vậy nên bạn được lệnh phải tìm một đường đi ngắn nhất từ đơn vị tới sở chỉ huy. Biết rằng bạn có thể đi sang ~4~ ô kề cạnh với ô đang đứng và mỗi ô ~(i,j)~ sẽ được miêu tả bằng một kí tự như sau:

• ~c(i,j) = .~, nếu đây là một ô bình thường có thể đi.
• ~c(i,j) = *~, đây là vùng nguy hiểm tuyệt đối không được đi vào.
• ~c(i,j) = S~, đây là đơn vị của bạn, sẽ chỉ có duy nhất một ô thế này xuất hiện.
• ~c(i,j) = T~, đây là sở chỉ huy, sẽ chỉ có duy nhất một ô thế này xuất hiện.

Input

• Dòng đầu tiên gồm ~2~ số nguyên ~n,m~, miêu tả kích thước bảng.
• ~n~ dòng sau, mỗi dòng gồm ~m~ kí tự miêu tả vùng đất.

Output

• In ra một dòng là đường đi ngắn nhất từ đơn vị tới sở chỉ huy. Nếu không có một đường đi nào như vậy, in ra ~-1~.

Điều kiện

• ~1 \le n,m \le 1000~

Ví dụ

Input 1:

3 4 
S...
....
...T

Output 1:

5

Input 2:

3 4 
S.*T
*.*.
*...

Output 2:

7

Tèo là một cậu bé sinh ra trong sự ghét bỏ của cả gia tộc, vì vậy từ nhỏ cậu đã không được chung sống với gia đình mình. Tuy nhiên, ngay khi họ nhìn thấy tiềm năng Tin học của Tèo, họ đã nhanh chóng chuộc lại Tèo vào dòng họ. Giờ đây, Tèo đang đứng trước cây gia phả của cả dòng họ, nhưng cậu lại không thể nhận ra bất cứ ai, kể cả chính bản thân mình. Nhằm thử thách khả năng Tin học của Tèo, hai bố của cậu là Đức và Khôi đã giải đáp danh tính của Tèo dưới dạng một bài toán, dựa vào chính cây gia phả của gia đình nọ.

Ta được biết tất cả các mối quan hệ vợ - chồng trong gia tộc của Tèo đều quang minh chính đại, nên ta mặc định cây gia phả của Tèo không tồn tại chu trình, và trừ Tèo ra, tất cả các thành viên đều có máu mủ với nhau, tức không có bất cứ ai tách ra sinh sống riêng. Nói cách khác, dòng họ Tèo là một đơn đồ thị vô hướng liên thông và không có chu trình. Ta cũng được biết hai bố Đức và Khôi, tuy chung một dòng họ, lại là hai người có khoảng cách xa nhất trong dòng họ, vậy nên bài toán hai bố cũng liên quan đến sự trùng hợp ấy.

Để cho Tèo biết về tình máu mủ sâu sắc giữa hai bố, cậu đã được hỏi: Với cây ~N \ (3 \leq N \leq 2 \times 10^5)~ đỉnh biểu diễn dòng họ Tèo, hai cụ muốn tìm đúng ~3~ đỉnh ~a, b, c~ sao cho số lượng tất cả những cạnh nằm trên ít nhất một đường đi đơn giữa ~(a, b), (b, c), (c, a)~ là lớn nhất. Ngoài ra, Tèo cũng cần tìm danh tính của ba người ~a, b, c~ này theo thứ tự ~a < b < c~ và số hiệu của ba người này là nhỏ nhất có thể. Tuy nhiên vì Tèo đã bận đi mua Light Novel, bạn sẽ là người giải quyết bài toán này!

Input

• Dòng đầu tiên chứa một số nguyên dương ~N \ (3 \leq N \leq 2 \ \times 10^5)~ là số nút tượng trưng cho số thành viên trong gia tộc.
• Trong ~N - 1~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~u_i, v_i \ (1 \leq u_i, v_i \leq N)~ thể hiện mối quan hệ cha - con giữa hai người có số hiệu ~u_i, v_i~.

Output

• Dòng đầu tiên in ra một số nguyên dương duy nhất là số cạnh lớn nhất được bao phủ bởi các đường đi đơn đôi một giữa ~a, b, c~.
• Dòng thứ hai in ra ba số nguyên dương ~a < b < c~ là ba người được chọn.

Subtasks

• Subtask ~1 \ (30\%)~: ~N \leq 200~.
• Subtask ~2 \ (30\%)~: ~N \le 2000~.
• Subtask ~3 \ (10\%)~: Cây có dạng đường thẳng.
• Subtask ~4 \ (30\%)~: Không có ràng buộc gì thêm.

Sample Input 1

4
1 2
1 3
2 4

Sample Output 1

3
1 3 4

Sample Input 2

8
1 2
2 3
1 4
4 5
2 6
5 7
6 8

Sample Output 2

7
3 7 8

Arya là một tsundere! Cô rất thích ăn đồ ngọt, nhất là kẹo mút và kẹo socola, nhưng không bao giờ tự mình đi mua. Do muốn làm Arya vui nên macknsa quyết định đi sẽ đi mua giúp cô (simp?).

Có ~n~ cửa hàng đồ ngọt, cửa hàng thứ ~i~ có độ ngon của những chiếc kẹo mút là ~a_i~ và kẹo socola là ~b_i~ và Arya muốn ăn kẹo trong ~q~ ngày. Do khó tính nên ngày thứ ~i~ Arya chỉ ăn kẹo ở các cửa hàng từ ~l_i~ đến ~r_i~. macknsa sẽ đi đến cửa hàng thứ ~i~ mua một cái kẹo mút, và đến cửa hàng thứ ~j~ mua một chiếc kẹo socola ~(l \le i < j \le r)~. Tuy nhiên, độ ngon của chiếc kẹo mút sẽ giảm đi một giá trị là khoảng cách đến cửa hàng thứ ~j~ (giảm ~j-i~).

macknsa muốn các bạn tìm cách mua sao cho độ ngon của các viên kẹo là lớn nhất để được Arya thưởng :3.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,q~ ~(1 \le n,q \le 2 \times 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ ~(1 \le a_i \le 10^9)~.
• Dòng thứ ba chứa ~n~ số nguyên dương ~b_i~ ~(1 \le b_i \le 10^9)~.

• ~q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~l~,~r~ ~(1 \le l < r \le n)~.

  Output

• In ra ~q~ dòng là đáp án của từng truy vấn.

Subtasks

• Subtask ~1~: ~n,q \le 1000~ ~(25\%)~
• Subtask ~2~: Không có ràng buộc gì thêm ~(75\%)~

Sample Input

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

Sample Output

3
7
2

Note:

• Ngày đầu tiên macknsa chọn mua cửa hàng thứ ~1~ và ~2~.
• Ngày thứ hai macknsa chọn mua của hàng thứ ~3~ và ~4~.
• Ngày thứ ba macknsa chọn mua cửa hàng thứ ~2~ và ~3~.

Trong số quý khách, có vị nào là thám tử không ạ?

Trên độ cao một vạn mét giữa không trung, câu nói ấy đã khởi đầu cho những chuyến phiêu lưu rực rỡ của siêu thám tử và trợ lý. Chúng tôi trải qua 6 năm chói lòa cùng nhau, với biết bao niềm vui, nỗi buồn, gặp gỡ và ly biệt. Để rồi tưởng như tôi đã có thể viên mãn ngâm mình trong khoảng lặng yên bình, cuộc sống thường nhật ấy không kéo dài được lâu. Đã có sự lạ thường diễn ra trong kí ức của toàn nhân loại, che giấu một mối nguy lớn hơn những 'Kẻ thù của thế giới' mà chúng tôi từng đối đầu. Thám tử đã chết. Không, phép màu đã mang ý chí ấy truyền lại cho những người kế cận. Và giờ là lúc bắt đầu chuyến phiêu lưu của các thám tử đương đầu với câu đố mà thế giới này đang ẩn giấu.

Thám tử bậc thầy cùng trợ thủ của cô đã nhận những khoảng trắng trong ký ức của hai người cùng những người bạn của họ như thể có ai đó đã thuyết phục họ phải chấp nhận với thứ hòa bình tạm bợ hiện tại. Với những manh mối của cố 'Người đưa tin', họ đang dần men theo những hành lang của trí nhớ để khôi phục lại kí ức thất lạc đó.

Với vai trò là một trong mười hai Người điều chỉnh - Những kẻ có trách nhiệm cân bằng cán cân giữa thiện và ác của thế giới, Thám tử bậc thầy có những đặc quyền riêng phục vụ cho công việc của cô, và một trong số đó là sự phục vụ của những Hắc phục - Một tổ chức gồm những thành viên mang trên mình những bộ vest đen, ẩn mình vào những góc tối của thành phố nhằm hoàn thành công việc tình báo. Trong nhiệm vụ lần này, Thám tử bậc thầy đã yêu cầu tìm những mảnh thông tin về chân tướng của kí ức thất lạc của nhân loại.

Theo dự tính, Thám tử bậc thầy cần tìm ~K~ mảnh thông tin khác nhau, và cô đã huy động được ~N~ quân tình báo từ Hắc phục, mỗi người được đánh số hiệu lần lượt từ ~1~ đến ~N~. Nhằm tối ưu thời gian tìm kiếm và hiệu suất, cô đã cử từng người trong số ~N~ người trên truy tìm một mảnh thông tin duy nhất, tức không có người nào được giao nhiệm vụ tìm kiếm nhiều hơn một mảnh thông tin. Cụ thể, ta có danh sách mảnh thông tin mà từng người phải tìm lần lượt là ~a_1, a_2, \dots, a_N~, dĩ nhiên ~1 \leq a_i \leq K \ \ \forall \ 1 \leq i \leq N~.

Chú ý: có thể có nhiều người được giao nhiệm vụ truy tìm một mảnh thông tin.

Trong khi chờ đợi họ hoàn thành nhiệm vụ, vị Thám tử bậc thầy đã thử đặt ra ~Q~ giả thiết: Thám tử sẽ chọn một dãy những người tình báo có số hiệu từ ~L~ đến ~R \ (1 \leq L \leq R \leq N)~ và đếm số tình huống hoàn thành công việc của họ. Một tình huống hoàn thành công việc được chọn là một cách loại bỏ một số người trong những người đang xét (có thể không loại bỏ người nào) sao cho những người còn lại đều tìm được tất cả mảnh thông tin từ ~1~ đến ~K~. Ở đây thám tử chấp nhận tình huống có nhiều người cùng tìm được một mảnh thông tin, miễn tất cả các mảnh thông tin đều được tìm thấy.

Là trợ thủ số một của Thám tử bậc thầy, hãy giúp cô đếm số tình huống hoàn thành công việc với mỗi giả thiết.

Input

• Dòng đầu tiên chứa ba số nguyên ~N, K, Q~ ~(1 \le K \le N \le 10^5; \ 1\le Q \le 10^5)~;
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, ..., a_N~ ~(1\le a_i\le K, 1\le i\le N)~;
• ~q~ dòng sau, mỗi dòng chứa hai số nguyên ~L, R~ ~(1\le L\le R\le N)~.

Output

Với mỗi giả thiết, in ra một số nguyên trên một dòng là số tìn huống hoàn thành công việc. Vì kết quả có thể rất lớn nên hãy in ra phần dư của kết quả sau khi chia cho ~10^9+7~.

Ví dụ

Input

4 3 2
1 2 1 3
2 4
1 4

Output

1
3

Giải thích

Thứ tự các tình huống hoàn thành công việc của:

• Giả thiết ~1~: ~(2, 3, 4)~;
• Giả thiết ~2~: ~(1, 2, 3, 4), (1, 2, 4), (2, 3, 4)~.

Scoring

• Subtask ~1 \ (25\%)~: ~N, Q\le 100~;
• Subtask ~2 \ (25\%)~: ~N, Q\le 5000~;
• Subtask ~3 \ (25\%)~: ~K\le 100~;
• Subtask ~4 \ (25\%)~: Không có ràng buộc gì thêm.

Bài đồ thị siêu cơ bản nên đề bài vô cùng ngắn gọn:

Quân có một đồ thị đầy đủ, vô hướng, có trọng số gồm ~n~ đỉnh. Trọng số của đỉnh thứ ~i~ là ~a_i~. Trọng số của cạnh nối giữa đỉnh ~u~ và đỉnh ~v~ là ~\frac{a_u + a_v}{gcd(a_u, a_v)}~. Cảm giác bài chưa đủ khó nên Quân vẽ thêm ~m~ cạnh nối nữa. Cạnh thứ ~i~ nối giữa hai đỉnh ~u_i~ và ~v_i~, và có trọng số là ~w_i~.

Hãy tính độ dài đường đi ngắn nhất từ đỉnh ~1~ tới mỗi đỉnh còn lại.

Input

• Dòng đầu chứa hai số nguyên không âm ~n, m~ ~(1 \le n \le 10^5, 0 \le m \le 10^4)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le 10^5)~.
• ~m~ dòng cuối cùng, 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, 1 \le w_i \le 10^5)~.

Output

• In ra ~n~ số nguyên không âm, số thứ ~i~ là độ dài đường đi ngắn nhất từ đỉnh ~1~ tới đỉnh ~i~.

Subtask

• Subtask ~1~ (~20\%~ số điểm): ~n \le 1000~
• Subtask ~2~ (~20\%~ số điểm): Dãy ~a~ đôi một giống nhau
• Subtask ~3~ (~20\%~ số điểm): ~m = 0; \ a_i \le 50 \ \forall i \in [1, n]~
• Subtask ~4~ (~20\%~ số điểm): ~m = 0~
• Subtask ~5~ (~20\%~ số điểm): Không có ràng buộc gì thêm

Sample input 1

3 1
1 2 3
2 3 1

Sample output 1

0 3 4