Cho dãy ~S~ gồm ~n~ chữ số từ 0 đến 9. Hãy tìm số lượng số tự nhiên chia hết cho 5 khác nhau là dãy con của ~S~. Vì kết quả rất lớn, nên lấy số dư khi chia cho ~10^9 + 7~.

Một số tự nhiên ~x~ là dãy con của ~S~ nếu tồn tại các chỉ số ~i_1, i_2, \dots, i_k~ (~1 \le i_1 < i_2 < \dots < i_k \le n~) sao cho ~S_{i_1}S_{i_2} \dots S_{i_k} = x~ và ~x~ không có chữ số 0 thừa ở đầu.

Yêu cầu: Tìm số lượng số tự nhiên chia hết cho 5 khác nhau là dãy con của ~S~.

Input

• Dòng đầu tiên ghi số test ~t~ (~1 \le t \le 10^6~). Tiếp theo là mô tả của ~t~ test.
• Dòng đầu tiên của test ghi một số nguyên dương ~n~ (~1 \le n \le 10^6~).
• Dòng tiếp theo ghi dãy ~S~ gồm ~n~ chữ số từ 0 đến 9.
• Dữ liệu đảm bảo tổng ~n~ của mọi test không vượt quá ~10^6~.

Output

• Với mỗi testcase, in ra đáp án trên một dòng.

Sample Input 1

4 
6 
177013 
3 
555 
10 
0123456789 
6 
130505 

Sample Output 1

6 
3 
17 
38

Năm mới đã đến, và Minh - lớp trưởng đội tuyển X - đã có một dự định: bắt cả đội tuyển đi chạy quanh trường nhân dịp đầu năm mới.

Trường X có ~N~ (~2 \le N \le 100000~) địa điểm được đánh số từ 1 đến ~N~ và ~(N - 1)~ con đường kết nối 2 địa điểm, và chắc chắn giữa 2 địa điểm có ít nhất 1 tuyến đường nối chúng. Minh muốn mọi người bắt đầu từ một địa điểm, và lặp lại thao tác sau ~(N - 1)~ lần: chọn một địa điểm chưa được đến bao giờ để đi từ điểm hiện tại. Để giúp mọi người khỏe hơn, khoảng cách giữa 2 địa điểm liên tiếp phải là một dãy không giảm.

Hay nói cách khác, Minh và các bạn cần tìm một dãy ~p[1], p[2], \dots, p[N]~ sao cho:

• ~p[1], p[2], \dots, p[N]~ tạo thành một hoán vị, tức là mỗi số từ 1 đến ~N~ xuất hiện đúng một lần.
• ~dist(p[i], p[i + 1]) \le dist(p[i + 1], p[i + 2])~ (~1 \le i \le N - 2~) với ~dist(a, b)~ là độ dài đường đi ngắn nhất giữa địa điểm ~a~ và địa điểm ~b~.

Yêu cầu: Hãy tìm một dãy như vậy, hoặc in ra "-1" nếu không có dãy nào thỏa mãn.

Input

• Dòng đầu tiên chứa số ~N~ (~2 \le N \le 100000~).
• Mỗi dòng trong ~(N - 1)~ dòng tiếp theo ghi 2 số ~a~ và ~b~, biểu thị có cạnh nối giữa 2 đỉnh ~a~ và ~b~. Input đảm bảo đồ thị liên thông.

Output

• In ra dãy ~n~ số là hoán vị thỏa mãn điều kiện đề bài, hoặc -1 nếu không có dãy nào thỏa mãn.

Sample Input 1

5 
1 2 
1 3 
2 4 
3 5 

Sample Output 1

1 2 3 4 5

Thành phố H được biết đến với cái tên “thiên đường tội phạm” có ~n~ (~n \le 2 \times 10^5~) giao lộ được nối với nhau bằng ~m~ (~m \le 2 \times 10^5~) con đường, đảm bảo tồn tại ít nhất một tuyến đường đi giữa 2 giao lộ bất kì.

Vào mỗi ngày trong ~q~ (~q \le 2 \times 10^5~) ngày liên tiếp, cục cảnh sát nhận được một tin báo rằng sẽ có một nhóm tội phạm di chuyển từ ~u~ tới ~v~. Để ngăn chặn nhóm tội phạm, cục cảnh sát có thể điều động duy nhất 1 nhóm cảnh sát canh giữ tại ~w~ (khác ~u~ và ~v~) với chi phí là ~a[w]~ sao cho mọi đường đi của tội phạm đi ~u~ tới ~v~ đều phải đi qua ~w~.

Yêu cầu: Hãy tìm chi phí nhỏ nhất để ngăn chặn nhóm tội phạm.

Input

• Dòng đầu ghi 2 số ~n, m~ là số giao lộ và số con đường trong thành phố (~n, m \le 2 \times 10^5~).
• Dòng thứ hai ghi ~n~ số ~a[1], a[2], \dots, a[n]~ là chi phí để điều động cảnh sát tới từng giao lộ (~a[i] \le 10^9~).
• Sau đó là ~m~ dòng, mỗi dòng ghi 2 số ~a, b~, thể hiện có 1 con đường nối 2 giao lộ ~a~ và ~b~.
• Dòng tiếp theo ghi số ngày ~q~ có tin báo tội phạm (~q \le 2 \times 10^5~).
• Dòng thứ ~i~ trong ~q~ dòng sau ghi 2 số ~u, v~ (~1 \le u, v \le n~) thể hiện 1 nhóm tội phạm di chuyển từ ~u~ tới ~v~ trong ngày thứ ~i~.

Output

• In ra ~q~ dòng, dòng thứ ~i~ là chi phí nhỏ nhất để ngăn chặn nhóm tội phạm ở ngày thứ ~i~, hoặc -1 nếu không thể ngăn chặn.

Sample Input 1

5 5
4 1 10 7 5
1 2
2 3
3 5
4 3
5 2
5
1 4
3 4
1 3
3 3
5 4

Sample Output 1

1
-1
1
-1
10

Tom và Jerry có một giá sách gồm ~m~ tầng, các tầng được đánh số từ ~1~ đến ~m~ từ trên xuống dưới. Mỗi tầng có ~n~ quyển sách, các quyển được đánh số từ ~1~ đến ~n~ từ trái sang phải, quyển sách thứ ~j~ ở tầng ~i~ được gọi là quyển sách ~(i, j)~ và có ~p_{ij}~ trang.

Tom thường xuyên dành thời gian để sắp xếp lại sách trong giá sách, mỗi lần Tom sẽ tráo đổi hai quyển sách ~(x, y)~ với ~(u, v)~. Jerry thường rủ Tom cùng đọc sách theo cách:

Jerry chọn hai số ~L, R~ sao cho ~1 \le L \le R \le m~ và cho Tom chọn một tầng sách ~s~ sao cho ~L \le s \le R~ và cả hai sẽ cùng đọc tất cả ~n~ quyển sách trên tầng đó. Tại một thời điểm, một quyển chỉ được đọc bởi một người và người đó đọc liên tục cho đến hết quyển sách. Thời gian để Tom hoặc Jerry đọc một trang sách là ~1~ giây. Cả Tom và Jerry đều đọc ~n~ quyển sách trên tầng ~s~ dù trước đó quyển sách đã đọc hay chưa, thời gian để hai bạn đọc hết tầng sách là thời gian cả hai đều đọc xong ~n~ quyển sách. Vì Tom muốn ưu tiên thời gian sắp xếp lại sách nên Tom sẽ lựa chọn tầng ~s~ để thời gian đọc là nhỏ nhất.

Cho dãy ~q~ hoạt động, mỗi hoạt động thuộc một trong hai loại:

• Loại 1 có dạng: ~1~ ~x~ ~y~ ~u~ ~v~, loại này sẽ tráo đổi hai quyển sách ~(x, y)~ với ~(u, v)~;
• Loại 2 có dạng: ~2~ ~L~ ~R~, loại này cần trả lại thời gian nhỏ nhất để đọc một tầng sách trong các tầng từ ~L~ đến ~R~.

Yêu cầu: Thực hiện lần lượt ~q~ hoạt động.

Input

• Dòng đầu chứa ba số nguyên dương ~m, n, q~ (~m \times n \le 10^6; q \le 10^6~);
• Dòng thứ ~i~ trong ~m~ dòng tiếp theo gồm ~n~ số nguyên ~p_{i1}, p_{i2}, \dots, p_{in}~ (~1 \le p_{ij} \le 10^6~);
• Dòng thứ ~k~ (~1 \le k \le q~) trong ~q~ dòng tiếp theo mô tả truy vấn.

Output

• Ghi ra lần lượt là câu trả lời cho các hoạt động loại 2.

Công ty của Jerry có ~n~ nhân viên, các nhân viên được đánh số từ ~1~ đến ~n~. Hiện tại công ty đang thực hiện hai dự án và cả ~n~ nhân viên đều tham gia hai dự án. Đối với mỗi dự án, nhân viên sẽ được tổ chức phân cấp theo mô hình cây. Một cây con gốc ~u~ sẽ tương đương với một nhóm do nhân viên ~u~ phụ trách, trong nhóm đó lại có thể có các nhóm con tương ứng là các cây con trong cây con gốc ~u~. Mỗi nhân viên tương ứng là một nút lá cũng được coi như trưởng nhóm của nhóm chỉ gồm chính bản thân mình. Chú ý rằng, hai dự án là độc lập và việc tổ chức phân cấp theo mô hình cây của hai dự án là độc lập và có thể khác nhau.

Sắp tới, Jerry muốn tổ chức lại nhân sự trong công ty. Với mỗi nhân viên ~u~, họ sẽ phải tự đánh giá hai giá trị ~a_u~ và ~b_u~. Trong đó, giá trị ~a_u~ là số lượng người ít nhất cần thiết trong nhóm mà ~u~ làm trưởng nhóm ở dự án thứ nhất để dự án đảm bảo vẫn được hoàn thành. Tương tự, giá trị ~b_u~ là số lượng người ít nhất cần thiết trong nhóm mà ~u~ làm trưởng nhóm ở dự án thứ hai để dự án đảm bảo vẫn được hoàn thành. Số người cần có được hiểu là số nút tối thiểu trong cây gốc ~u~ (có thể có hoặc không có ~u~).

Yêu cầu: Hãy giúp Jerry tính số người ít nhất cần giữ lại mà vẫn bảo đảm hai dự án được hoàn thành.

Input

• Dòng đầu chứa số nguyên dương ~n~;
• Dòng thứ hai gồm ~n~ số nguyên, số thứ ~u~ cho biết trưởng nhóm trực tiếp của nhân viên ~u~ trong dự án thứ nhất, nếu ~u~ là gốc của cây thì giá trị này bằng ~0~;
• Dòng thứ ba gồm ~n~ số nguyên, số thứ ~u~ cho biết trưởng nhóm trực tiếp của nhân viên ~u~ trong dự án thứ hai, nếu ~u~ là gốc của cây thì giá trị này bằng ~0~;
• Dòng thứ tư gồm ~n~ số nguyên không âm ~a_1, a_2, \dots, a_n~;
• Dòng thứ năm gồm ~n~ số nguyên không âm ~b_1, b_2, \dots, b_n~.

Output

• Ghi ra một số nguyên là số người ít nhất cần giữ lại mà vẫn bảo đảm hai dự án được hoàn thành.

Bác Tom là người gác đêm ở một viện bảo tàng. Viện bảo tàng này là một ngôi nhà có các bức tường vuông góc với nhau. Ta có thể vẽ một hệ trục tọa độ sao cho các cạnh thể hiện tường trên sơ đồ mặt bằng bảo tàng song song với trục tọa độ. Các cạnh này tạo thành một đường khép kín không tự cắt. Ngoài ra, sơ đồ mặt bằng còn có một tính chất như sau: mỗi đường thẳng ~y = c~ hoặc ~x = c~ không có phần chung với các điểm bên trong bảo tàng hoặc là các điểm chung này làm thành một đoạn thẳng.

Cứ mỗi giờ bác Tom phải đi duyệt một lần, quan sát mọi nơi trong bảo tàng. Nếu ~A~ là một điểm trên đường đi của bác Tom, ~B~ là một điểm trong viện bảo tàng thì từ ~A~ có thể nhìn thấy ~B~ nếu đoạn ~AB~ nằm gọn trong bảo tàng (có thể có một hay nhiều điểm chung với cạnh của sơ đồ). Là một người đã nhiều tuổi, bác Tom không muốn đi lại quá nhiều, vì vậy bác chọn một đường đi ngắn nhất mà dọc theo đường đi đó bác quan sát hết mọi điểm trong bảo tàng. Bác đặt một cái ghế ở một vị trí trên đường đi, khi đến giờ tuần tra bác đứng dậy đi hết con đường đã chọn rồi quay lại ghế ngồi của mình. Cũng có thể có trường hợp bác không cần đi đâu cả nếu có địa điểm cho phép từ đó quan sát toàn bộ bảo tàng.

Yêu cầu: Cho ~n~ (~n \ge 4~) là số điểm góc của bảo tàng và tọa độ ~(x_i, y_i)~ của điểm góc thứ ~i~ (~1 \le i \le n~). Hãy xác định độ dài con đường bác Tom phải đi ở mỗi lần tuần tra. Thông tin về các đỉnh được cho theo trình tự ngược chiều kim đồng hồ.

Input

• Dòng đầu tiên chứa số nguyên ~n~;
• Dòng thứ ~i~ trong ~n~ dòng sau chứa hai số nguyên ~x_i, y_i~.

Output

• Ghi ra một số thực là độ dài đường đi một lần tuần tra với độ chính xác 5 chữ số sau dấu chấm thập phân.