Cho đồ thị vô hướng không có trọng số gồm ~n~ đỉnh và ~m~ cạnh. Hãy đếm số thành phần liên thông của đồ thị đã cho.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,m~.
• ~m~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~u~ và ~v~ miêu tả cạnh ~(u,v)~.

Output

• In ra số thành phần liên thông của đồ thị.

Điều kiện

• ~ 1 \le n,m \le 10^5~.

Ví dụ

Input 1:

4 3
1 2
2 3
3 4

Output 1:

1

Input 2:

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

Output 2:

2

Đất nước ~ABC~ gồm ~n~ thành phố, có ~m~ con đường hai chiều với độ dài là ~1~ nối giữa một cặp thành phố. Có ~k~ khách du lịch, vị khách thứ ~i~ đang ở thành phố ~a_i~. Hiện đang có một sự kiện xảy ra ở thành phố ~b~, với mỗi khách du lịch, hãy in ra con đường ngắn nhất mà người đó phải đi để tới sự kiện này.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,m,k~.
• ~m~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~u~ và ~v~ miêu tả con đường ~(u,v)~.
• Dòng tiếp theo gồm ~k~ số nguyên dương miêu tả thành phố mà vị khách thứ ~i~ đang ở.
• Dòng cuối cùng chứa số nguyên dương ~b~ - thành phố nơi diễn ra sự kiện.

Output

• Với mỗi vị khách, in ra con đường ngắn nhất mà người đó phải đi để tới sự kiện.

Điều kiện

• ~ 1 \le n,m,k \le 2*10^5~.

Subtask

• ~50\%~ số điểm: ~n,m,k \le 1000~.
• ~50\%~ số điểm: Không giới hạn gì thêm.

Ví dụ

Input 1:

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

Output 1:

3 2 1

Input 2:

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

Output 2:

1 1 -1

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

Năm ~1976~, "Định lý bản đồ bốn màu" đã được chứng minh với sự hỗ trợ của máy tính. Định lý này cho rằng mọi bản đồ có thể được tô màu chỉ bằng bốn màu, theo cách mà không có vùng nào được tô màu sử dụng cùng màu với vùng lân cận.

Tuy nhiên, ở đây bạn được yêu cầu giải một bài toán tương tự nhưng đơn giản hơn. Bạn cần kiểm tra xem một đồ thị được cho có thể được "tô màu" hay không. Một đồ thị có thể coi là được "tô màu", nếu ta có thể gán một màu (chỉ sử dụng đúng hai màu) cho các nút sao cho không có hai nút liền kề nào có cùng màu.

Đồ thị được cho có một vài điều kiện như sau:

• Không có khuyên.
• Đồ thị vô hướng.
• Đồ thị liên thông.

Input

• Dòng thứ nhất gồm số nguyên dương ~t~ miêu tả số test case.
• Đối với mỗi test case:
  • Dòng thứ nhất chứa số nguyên dương ~n~ miêu tả đỉnh của đồ thị. Lưu ý, các đỉnh trong đồ thị được đánh dấu từ ~0~ tới ~n-1~.
  • Dòng thứ hai gồm số nguyên dương ~m~ miêu tả số cạnh của đồ thị.
  • ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~u,v~ miêu tả cạnh ~(u,v)~.

Output

• Với mỗi test case, in ra "BICOLORABLE." nếu có thể "tô màu" đồ thị, ngược lại in ra "NOT BICOLORABLE.".

Constraints

• ~1 \le t \le 20~
• ~1 \le n,m \le 200~

Sample Input 1:

3

3
3
0 1
1 2
2 0

3
2
0 1
1 2

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

Sample Output 1:

NOT BICOLORABLE.
BICOLORABLE.
BICOLORABLE.

Nitori Kawashiro cần thiết kế hệ thống cáp treo 2 chiều giữa ~n~ địa điểm. Biết rằng nếu có đường đi giữa địa điểm ~a~ tới địa điểm ~b~ và từ địa điểm ~b~ tới địa điểm ~c~ thì có thể đi từ ~a~ đến ~c~. Hãy cho biết cần xây dựng ít nhất bao nhiêu đường đi trực tiếp giữa 2 địa điểm để kết nối ~m~ cặp địa điểm cho trước.

Nói tóm lại, từ đồ thị được cho ban đầu, hãy tìm cách giữ lại ít cạnh nhất sao cho số vùng liên thông được giữ nguyên.

Input

• Dòng đầu tiên gồm 2 số tự nhiên ~n, m \le 10^5~.
• ~m~ dòng tiếp theo mỗi dòng gồm 2 địa điểm ~u, v \le n~.

Output

• In ra một số ~p~ là số lượng đường đi trực tiếp giữa 2 địa điểm.
• ~p~ dòng sau mỗi dòng in ra 2 số ~u, v~ nghĩa là xây đường đi giữa 2 địa điểm ~u~ và ~v~.

Sample Test

Input:

4 2
1 2
1 4

Output:

2
1 2
2 4

Đất nước U có ~n~ thành phố, đánh số từ 1 đến ~n~. Các thành phố được nối với nhau bởi hệ thống giao thông gồm m tuyến đường hai chiều, mỗi tuyến đường nối trực tiếp một cặp thành phố, đảm bảo luôn có đường đi lại giữa hai thành phố bất kì trong nước (trực tiếp hoặc đi qua một số thành phố khác). Giữa hai thành phố bất kì không có quá một tuyến đường nối trực tiếp.

Có tổng cộng ~b~ kho lương thực được đặt trên khắp cả nước, mỗi kho nằm ở một thành phố khác nhau. Để bảo vệ đất nước khỏi quân xâm lược, Thủ tướng U đã chọn ra ~r~ thành phố khác nhau để đặt trại quân sự.

Yêu cầu: Để giải quyết vấn đề lương thực cho quân doanh, với mỗi thành phố được đặt trại quân sự, nhiệm vụ của bạn là tính toán số tuyến đường ít nhất cần đi nếu xuất phát từ thành phố đó đến một kho lương thực bất kì.

Input

• Dòng thứ nhất gồm bốn số nguyên: ~n,m,b,r\ (2 \le n \le 5.10^5; 1 \le m \le 5.10^5; 1 \le b,r \le n)~
• Dòng thứ hai gồm ~b~ số nguyên là chỉ số của các thành phố được đặt kho lương thực;
• Dòng thứ ba gồm ~r~ số nguyên là chỉ số của các thành phố được đặt trại quân sự;
• ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u~ và ~v~ thể hiện có một tuyến đường hai chiều nối trực tiếp hai thành phố ~u~ và ~v~.

Output

• Xuất ra ~r~ số nguyên trên cùng một dòng là kết quả tính được của các thành phố được đặt trại quân sự theo thứ tự của dữ liệu.

Subtask

• Subtask 1: (40% số test): ~n \le 5000~
• Subtask 2: (60% số test): Không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

1 2 1

Explanation 1

• Thành phố ~1~: ~1 → 2~
• Thành phố ~4~: ~4 → 3~
• Thành phố ~5~: ~5 → 4 → 3~

Hai con thiên nga đang ở trong một cái hồ lớn, nhưng chúng lại đang bị chia cắt bởi băng đóng trong hồ nước. Hồ nước có dạng hình chữ nhật được chia thành ~r~ dòng ~c~ cột. Một số ô trong hồ bị băng đóng. Mùa xuân tới dần, băng trong hồ tan dần – mỗi ngày băng ở tất cả những ô tiếp xúc với nước đang ấm dần trong hồ (tức là kề cạnh một ô không bị đóng băng) sẽ tan ra.

Thiên nga có thể di chuyển tự do ở những ô chứa nước nhưng không thể đi qua những ô bị đóng băng. Bạn hãy tính xem sau bao nhiêu ngày thì đôi thiên nga của chúng ta có thể gặp nhau

Input

• Dòng đầu tiên chứa 2 số ~r~ và ~c~, ~1 \le r, c \le 1500~.
• Mỗi dòng trong ~r~ dòng tiếp theo chứa ~c~ kí tự mô tả hồ nước tại thời điểm hiện tại: '.' (dot) thể hiện 1 ô chứa nước, 'X' thể hiện 1 ô bị đóng băng, và 'L' thể hiện ô có thiên nga. Có chính xác 2 ô chữ L.

Output

• Một dòng duy nhất chứa số ngày đôi thiên nga có thể gặp nhau.

Example

Input

10 2
.L
..
XX
XX
XX
XX
XX
XX
..
.L

Output

3

Trên bảng kích thước ~n \times m~, máy tính chọn ngẫu nhiên một số ô là hang rắn được kí hiệu bởi kí tự ~+~. Người chơi cần di chuyển từ vị trí là ô chứa kí tự P đến ô chứa kí tự C. Một cách di chuyển được gọi là thông minh nếu càng tránh xa các ô là hang rắn càng tốt. Khoảng cách hai ô ~(x,y)~ và ~(u,v)~ được tính theo khoảng cách Manhattan: ~|x-u|+|y-v|~. Yêu cầu: Tìm cách di chuyển để trong quá trình di chuyển khoảng cách tới ô là hang rắn ngắn nhất là xa nhất.

Input

• Dòng đầu chứa hai số nguyên ~n, m~ ~(n,m \le 2000)~.
• Tiếp theo là ~m~ hàng, mỗi hàng chứa kí tự là một trong các kí tự: ~'+'~ (hang rắn), ~'P'~ (xuất phát), ~'C'~ (đích), ~'.'~ (ô tự do).

Output

• Gồm một dòng chứa một số là khoảng cách tìm được.

Sample Input 1

4 5
P....
.....
+++..
....C

Sample Output 1

2

Cho một đồ thị vô hướng gồm ~n~ đỉnh ~m~ cạnh. Cạnh ~i~ nối giữa đỉnh ~u_i~ và ~v_i~ và có kí tự ~c_i~ được viết lên trên nó.

Hãy tìm một đường đi từ ~1~ đến ~n~ ngắn nhất mà sau khi viết các kí tự có được khi đi qua các cạnh là một xâu palindrome. Nếu không tồn tại bất kì đường đi nào thỏa mãn là palindrome, in ra ~-1~.

Lưu ý: Đồ thị có thể tồn tại khuyên và cạnh lặp, các đỉnh và cạnh có thể đi qua lại nhiều lần.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n, m~ ~(1 \le n, m \le 1000)~.
• ~m~ dòng tiếp theo, mỗi dòng gồm ~u_i, v_i, c_i~ mô tả cạnh thứ ~i~ của đồ thị.

Output

• Nếu tồn tại một đường đi tạo ra xâu palindrome, in ra độ dài ngắn nhất có thể. Nếu không, in ra ~-1~.

Sample Input 1

4 5
1 1 a
1 2 a
2 3 a
3 4 b
4 4 a

Sample Output 1

5

Explanation 1

Đi qua các cạnh ~2, 3, 4, 5, 5~, ta nhận được xâu aabaa.

Sample Input 2

3 4
1 1 a
1 2 a
2 3 b
3 3 b

Sample Output 2

-1

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)~.

Công việc này chưa bao giờ là dễ dàng. Một vài ô đã bị địch cài bom và không biết khi nào sẽ phát nổ. Bạn chỉ biết rằng loại bom này có sức công phá là ~r~, có nghĩa là nếu bom ở ô ~(i,j)~, khi nó phát nổ thì các ô ~(u,v)~ thỏa mãn ~|i-u| + |j-v| \le r~ sẽ bị tàn phá (ô ~(i,j)~ và ~(u,v)~ đều nằm trong bảng). Những ô ~(u,v)~ như vậy gọi là những ô bị ảnh hưởng bởi bom.

Đây là tài liệu mật, tất nhiên chỉ huy của bạn không muốn nhận một sự rủi ro nào, 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 sao cho không được đi qua ô nào bị ảnh hưởng bởi bom. 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) =~ +, đây là ô có bom, như đã nói, các ô nằm cách ô này khoảng cách không quá ~r~ (kể cả chính nó) sẽ không thể đ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 ~3~ số nguyên ~n,m,r~, miêu tả kích thước bảng và vùng ảnh hưởng của bom.
• ~n~ dòng sau, mỗi dòng gồm ~m~ kí tự miêu tả vùng đất.
• Dữ liệu luôn đảm bảo ô chứa kí tự ~S~ và ~T~ không bị ảnh hưởng bởi ô chứa bom nào.
  
  

Output

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

Constraints

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

Subtasks

• ~20\%~ số điểm: Không có ô nào có ~c(i,j) = *~ hoặc ~c(i,j) = +~.
• ~20\%~ số điểm: ~r = 0~.
• ~30\%~ số điểm: ~n,m \le 100~.
• ~30\%~ số điểm: Không có ràng buộc gì thêm.
  
  

Sample Test 1

Input:

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

Output:

5

Sample Test 2

Input:

3 4 0
S.+T
*.*.
*...

Output:

7

Sample Test 3

Input:

4 4 1
S..*
*...
+.*.
.T..

Output:

8

Mrtee đang lặn lội trên con đường tìm ma pháp sư Marisa thì có một con Rùa và một con Thỏ cãi nhau xem ai nhanh hơn. Chúng quyết định giải quyết việc tranh luận bằng một cuộc thi chạy đua. Chúng đồng ý lộ trình và bắt đầu cuộc đua.

Thỏ xuất phát nhanh như tên bắn và chạy thục mạng rất nhanh, khi thấy rằng mình đã khá xa Rùa, Thỏ nghĩ nên nghỉ cho đỡ mệt dưới một bóng cây xum xê lá bên vệ đường và nghỉ thư giãn trước khi tiếp tục cuộc đua.

Vì quá tự tin vào khả năng của mình, Thỏ ngồi dưới bóng cây và nhanh chóng ngủ thiếp đi trên đường đua. Rùa từ từ vượt qua Thỏ và sớm kết thúc đường đua.

Khi Thỏ thức dậy thì rùa đã đến đích và trở thành người chiến thắng. Thỏ giật mình tỉnh giấc và nhận ra rằng nó đã bị thua.

Không thể chấp nhận sự thật, Thỏ quyết định tái đấu. Lần này, thay vì dùng một trò thiên về sức lực, Thỏ quyết định thách đấu bằng cách đố Rùa một câu hỏi đầy hóc búa.

Cho đồ thị vô hướng gồm ~n~ đỉnh và ~m~ cạnh, không có khuyên và cạnh lặp.

Để tạo ra được một đồ thị có độ đẹp, ta cần điền các số nguyên dương ~c~ trên mỗi đỉnh (~c~ chỉ có thể là ~1~, ~2~, hoặc ~3~), sao cho với mỗi cạnh, tổng của hai số được điền trên ~2~ đỉnh được kết nối bởi cạnh đó là một số lẻ.

Thỏ đố Rùa có thể đếm số cách để điền các số ~1,2,3~ lên mỗi đỉnh sao cho tạo ra được một đồ thị đẹp. Do con số này có thể rất lớn, hãy in nó ra theo ~modulo~ ~998244353~.

Lưu ý: Rùa phải điền đúng một số trên mỗi đỉnh.

Để cho câu đố thêm phần học búa, Thỏ sẽ hỏi ~q~ câu có dạng như vậy.

Rùa dù là một sinh vật cute nhưng không giỏi đồ thị cho lắm, hãy giúp Rùa hoàn thành bài toán này nhé!

Input

• Dòng đầu tiên gồm số nguyên dương ~q~ miêu tả số câu hỏi.
• Đối với mỗi câu hỏi:
  • Dòng đầu tiên ~2~ số nguyên dương ~n,m~ miêu tả số đỉnh và cạnh của đồ thị.
  • ~m~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên dương ~u_i,v_i~ ~(1 \le u_i,v_i \le n, u_i \neq v_i)~ miêu tả cạnh thứ ~i~.

Output

• Với mỗi câu hỏi, in ra một dòng là số nguyên duy nhất là số cách điền thỏa mãn sau khi lấy phần dư cho ~998244353~.

Điều kiện

• ~1 \le q \le 3 \times 10^5~.
• ~1 \le n,m \le 3 \times 10^5~.
• Dữ liệu đảo bảo rằng tổng ~n~ trong tất cả các câu hỏi không vượt quá ~3 \times 10^5~, tương tự với tổng ~m~.

Subtask

• ~50\%~ số điểm: ~n \le 10, q \le 10~.
• ~30\%~ số điểm: Trong mọi câu hỏi, đồ thị có dạng cây.
• ~20\%~ số điểm: Không có ràng buộc gì thêm.

Ví dụ

Input:

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

Output:

0
4

Giải thích:

Ở câu hỏi đầu tiên, không có cách điền nào thỏa mãn.

Ở câu hỏi thứ hai, có ~4~ cách điền như sau:

• Điền số ~1~ vào đỉnh ~1~, số ~2~ vào đỉnh ~2~.
• Điền số ~3~ vào đỉnh ~1~, số ~2~ vào đỉnh ~2~.
• Điền số ~2~ vào đỉnh ~1~, số ~1~ vào đỉnh ~2~.
• Điền số ~2~ vào đỉnh ~1~, số ~3~ vào đỉnh ~2~.

Cho dãy số nguyên ~a~ gồm ~n~ phần tử. Hãy tính tổng của ~|a_i-a_j|~ với mọi cặp ~(i,j)~ thỏa mãn ~1 \le i < j \le n~.

Input

• Dòng đầu gồm ~1~ số nguyên ~n~ ~(1 \le n \le 10^5)~.
• Dòng sau gồm ~n~ số nguyên miêu tả dãy ~a~ ~(|a_i| \le 10^6)~

Output

• In ra kết quả tìm được.

Sample Test

Input

3
5 1 2

Output

8

Cho số ~n~ và dãy số nguyên ~a~ gồm ~n~ phần tử, hãy tìm đoạn con liên tiếp dài nhất của dãy ~a~ có trung bình cộng lớn hơn hoặc bằng ~k~ cho trước.

Input

• Dòng đầu gồm 2 số nguyên ~n~ ~(1 \le n \le 10^5)~ và ~k~ ~(|k| \le 10^6)~.
• Dòng sau gồm ~n~ số nguyên miêu tả dãy ~a~ ~(|a_i| \le 10^6)~

Output

• In ra một số nguyên là độ dài của dãy con liên tiếp dài nhất thỏa mãn.

Sample Test

Input

7 3
1 5 2 3 1 4 1

Output

5

Trong cuộc thám hiểm gần đây, bạn đã phát hiện ra một hầm kho báu có thể được biểu diễn dưới dạng lưới với ~N~ hàng (được đánh số từ ~1~ đến ~N~) và ~M~ cột (được đánh số từ ~1~ đến ~M~). Ô ở hàng ~r~ và cột ~c~ được ký hiệu là ~(r, c)~. Ô ~(r, c)~ chứa kho báu nếu ~A_{r,c} = 1~, và ô đó trống nếu ~A_{r,c} = 0~.

Có ~Q~ kịch bản độc lập. Đối với mỗi kịch bản, bạn bắt đầu ở ô ~(R, C)~ và bạn muốn mang chính xác ~K~ kho báu trở về ô ~(R, C)~. Trong một giây, bạn có thể di chuyển đến bất kỳ ô nào kề bên theo hướng ngang, dọc hoặc chéo với ô bạn đang đứng, như được minh họa trong hình dưới đây. Do kho báu rất lớn, bạn chỉ có thể mang mỗi lần một kho báu, nghĩa là bạn phải mang kho báu trở về ô ~(R, C)~ trước khi lấy kho báu tiếp theo hoặc để hoàn thành kịch bản. Hành động nhặt hoặc bỏ kho báu không tốn thời gian.

Đối với mỗi kịch bản, xác định thời gian tối thiểu cần thiết (tính bằng giây) để mang ~K~ kho báu về ô ~(R, C)~ nếu bạn bắt đầu ở ô ~(R, C)~. Vì tất cả các kịch bản đều độc lập với nhau, nên sau mỗi kịch bản, các kho báu sẽ được trở lại vị trí ban đầu.

Input

• Dòng đầu tiên gồm hai số nguyên ~N~ và ~M~ (~1 \leq N, M \leq 1000~).
• Mỗi dòng trong ~N~ dòng tiếp theo bao gồm một chuỗi nhị phân ~A_i~ có độ dài ~M~. Ký tự thứ ~j~ của chuỗi ~A_i~ mô tả ô ~(i, j)~: là ~1~ nếu ô ~(i, j)~ chứa kho báu và là ~0~ nếu ô ~(i, j)~ trống. Số lượng kho báu trong hầm ít nhất là một.
• Dòng tiếp theo chứa một số nguyên ~Q~ (~1 \leq Q \leq 2 \times 10^4~).
• Mỗi dòng trong ~Q~ dòng tiếp theo gồm ba số nguyên ~R~, ~C~ và ~K~ (~1 \leq R \leq N~; ~1 \leq C \leq M~; ~1 \leq K~) mô tả mỗi kịch bản. Giá trị của ~K~ không vượt quá số lượng kho báu trong hầm.

Output

• Đối với mỗi kịch bản, xuất ra một số nguyên trên một dòng riêng biệt biểu thị thời gian tối thiểu (tính bằng giây) để mang ~K~ kho báu về ô ~(R, C)~ nếu bạn bắt đầu ở ô ~(R, C)~.

Sample

Input 1

5 5
11000
01011
10111
00101
10010
6
1 1 1
1 2 4
3 1 13
1 4 5
2 5 3
3 3 8

Output 1

0
8
64
16
4
20

Input 2

1 6
000111
3
1 1 2 
1 1 1
1 6 3

Output 2

14
6
6

Cho hai dãy ~a~ và ~b~ gồm ~n~ phần tử nguyên dương. Bạn được nhận thêm một số nguyên dương ~k~, hãy đếm số cặp ~(i,j)~ ~(1 \le i,j \le n)~ sao cho ~\overline{a_ib_j}~ ~\vdots~ ~k~.

Nói cách khác, hãy đếm số cặp ~(i,j)~ sao cho số nguyên dương ~X~ được tạo bởi cách viết liền ~a_i~ và ~b_j~ với nhau chia hết cho số nguyên dương ~K~ cho trước.

Ví dụ:

• ~a_i = 5, b_j = 77 \Rightarrow X = 577~
• ~a_i = 66, b_j = 99 \Rightarrow X = 6699~

Input

• Dòng đầu tiên gồm số hai nguyên dương ~n~ và ~k~ ~(1 \le n,k \le 3 \times 10^5)~
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~ ~(1 \le a_i \le 3 \times 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~b_1,b_2,...,b_n~ ~(1 \le b_i \le 3 \times 10^5)~.

Output:

• Gồm một dòng in ra số cặp ~(i,j)~ thỏa mãn.

Subtask:

• Subtask ~1~ (~40\%~ số điểm): ~n \le 2000~.
• Subtask ~2~ (~30\%~ số điểm): ~a_i,b_j \le 2000~ ~\forall i,j \in [1,n]~.
• Subtask ~3~ (~30\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

4 3
1 4 3 6
11 2 4 21 

Sample Output 1

6

Explanation 1

Có các cặp sau:

• ~(1,1) = 111~
• ~(1,2) = 12~
• ~(2,1) = 411~
• ~(2,2) = 42~
• ~(3,4) = 321~
• ~(4,4) = 621~

Chặt nhị phân là một kĩ thuật tìm kiếm quen thuộc đối với tất cả các lập trình viên. Một dãy số ~a~ là một dãy có thể chặt nhị phân được nếu như nó là một dãy số đồng biến. Cụ thể hơn, dãy đồng biến là dãy thoả mãn tính chất: ~(a_i - a_j) \cdot (a_j - a_k) \ge 0 \ \ \forall 1 \le i < j < k \le n~. Chú ý rằng theo định nghĩa này, mọi dãy số có không, một hoặc hai phần tử đều là dãy đồng biến.

Cho dãy số ~a_1, a_2, \ldots, a_n~, hãy đếm xem có bao nhiêu dãy con khác nhau của dãy này là dãy đồng biến.

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

Một dãy ~b~ được gọi là dãy con của dãy ~a~ nếu như ta có thể bỏ bớt một vài phần tử của ~a~ và giữ nguyên thứ tự của các phần tử còn lại để thu được dãy ~b~.

Hai dãy con được gọi là khác nhau nếu tồn tại một vị trí ~i~ sao cho phần tử thứ ~i~ của dãy ~a~ được bỏ đi để tạo ra dãy con thứ nhất, nhưng không được bỏ đi để tạo ra dãy con thứ hai.

Input

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

Output

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

Subtask

• Subtask ~1~ (~20\%~ số điểm): ~n \le 20~; Dãy ~a~ là một hoán vị của ~n~ số nguyên dương đầu tiên
• Subtask ~2~ (~20\%~ số điểm): ~n \le 80~; Dãy ~a~ là một hoán vị của ~n~ số nguyên dương đầu tiên
• Subtask ~3~ (~20\%~ số điểm): ~n \le 300~; Dãy ~a~ là một hoán vị của ~n~ số nguyên dương đầu tiên
• Subtask ~4~ (~20\%~ số điểm): ~n \le 5000~; Dãy ~a~ là một hoán vị của ~n~ số nguyên dương đầu tiên
• Subtask ~5~ (~10\%~ số điểm): Dãy ~a~ là một hoán vị của ~n~ số nguyên dương đầu tiên
• Subtask ~6~ (~10\%~ số điểm): Không có ràng buộc gì thêm

Sample input 1

5
4 2 1 5 3

Sample output 1

17

Explaination

Các dãy con đồng biến là:

• []
• [4], [2], [1], [5], [3]
• [4, 2], [4, 1], [4, 5], [4, 3], [2, 1], [2, 5], [2, 3], [1, 5], [1, 3], [5, 3]
• [4, 2, 1]

Cho một cây gồm ~n~ đỉnh gồm ~n-1~ cạnh. Cạnh thứ ~i~ có dạng ~(u_i,v_i, w_i)~, kết nối đỉnh ~u_i~ với đỉnh ~v_i~ và có độ dài là một số nguyên dương ~w_i~.

Gọi ~D(u,v)~ là khoảng cách giữa hai đỉnh ~u~ và ~v~ trên cây (được tính bằng tổng trọng số trên cạnh mà đường đi từ ~u~ tới ~v~ đi qua). Ta có hàm ~S(i)~ là tổng khoảng cách từ ~i~ tới tất cả các đỉnh trên cây:

• ~S(i) = \sum_{u=1}^{n} D(i,u)~.

Với mỗi đỉnh ~u~ trên cây, bạn được phép thử gán giá trị của một cạnh bất kì trên cây bằng ~0~ (tức là gán một giá trị ~w_i = 0~), sao cho giá trị ~S(u)~ mới, ta tạm gọi là ~S(u)'~ là nhỏ nhất có thể. Lưu ý rằng, mỗi lần thử là độc lập với nhau, ta không thực sự gán cạnh nào bằng ~0~ trong cây gốc cả.

Để tránh biến bài toán quá khó, với mỗi lần thử, các bạn không cần in ra ~S(u)'~, mà chỉ cần in ra độ chênh lệch giữa hai giá trị cũ và mới, nói cách khác in ra ~S(u) - S(u)'~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ ~(1 \le n \le 3 \times 10^5)~
• ~n-1~ dòng sau, dòng thứ ~i~ gồm 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^6)~ miêu tả cạnh thứ ~i~ của cây.

Output:

• Gồm một dòng gồm ~n~ số nguyên, số thứ ~i~ là ~S(i)~ nhỏ nhất thu được nếu ta thử gán tối ưu nhất có thể.

Subtask:

• Subtask ~1~ (~20\%~ số điểm): ~n \le 200~.
• Subtask ~2~ (~20\%~ số điểm): ~u_i = i, v_i = i+1~ ~\forall i \in [1,n-1]~.
• Subtask ~3~ (~20\%~ số điểm): ~w_i = 1~ với mọi ~i~ và ~n \le 2000~.
• Subtask ~4~ (~20\%~ số điểm): ~w_i = 1~ với mọi ~i~.
• Subtask ~5~ (~20\%~ số điểm): Không có giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

6 8 6 6 30 15

Explanation 1

Đối với đỉnh ~1~, giả sử ta gán cạnh ~(3,5) = 0~, ta sẽ giảm được ~S(1)~ đi một lượng là ~6~ của ~D(5,1)~.

Đối với đỉnh ~2~, giả sử ta gán cạnh ~(1,2) = 0~, ta sẽ giảm được ~S(2)~ đi một lượng là ~8~.

Với đỉnh ~5~, cách gán tối ưu nhất là gán ~(3,5) = 0~.

Với đỉnh ~6~, ta gán ~(2,6) = 0~ để thu được kết quả là giảm đi ~15~ đơn vị.