Cho phân số ~P/Q~, tiến hành biểu diễn phân số trong hệ cơ số thập phân, sau khi loại bỏ dấu chấm thập phân (dấu ngăn cách giữa phần nguyên và phần thực) ta nhận được một xâu số có độ dài vô hạn. Đánh số các kí tự của xâu bắt đầu từ 1, để khảo sát phân số, với một xâu mẫu người ta muốn tìm vị trí xuất hiện thứ ~k~ của ~X~ trong ~S~.

Yêu cầu: Cho ~P, Q, k~ và xâu ~X~, hãy xác định vị trí xuất hiện thứ ~k~ của ~X~ trong ~S~, trong đó ~S~ là biểu diễn của phân số ~P/Q~ trong hệ cơ số thập phân sau khi loại bỏ dấu chấm ngăn cách giữa phần nguyên và phần thực.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~P, Q, k~ (~0 < P, Q, k \le 10^6~);
• Dòng thứ hai chứa một xâu số ~X~ có độ dài không vượt quá ~10^5~.

Output

• Ghi ra một số là vị trí xuất hiện thứ ~k~ của ~X~ trong ~S~, nếu không tồn tại ghi số 0.

Sample Input 1

3 7 2
2

Sample Output 1

8

Sample Input 2

3 5 2
00

Sample Output 2

3

Có ~n~ người đánh số từ 1 đến ~n~ xếp thành một hàng và cùng nhau chơi trò chơi truyền tin. Người thứ ~i~ (~1 \le i \le n~) có độ trễ khi truyền tin là ~d_i~, khi đó độ trễ người thứ ~i~ truyền tin cho người thứ ~j~ (~1 \le i \le j \le n~) được tính bằng ~D(i, j) = \max\{d_i, d_{i+1}, \dots, d_j\}~.

Người quản trò muốn tìm ra ~k~ (~1 \le k \le n~) người chơi để tổng độ trễ liên lạc là nhỏ nhất. Một cách hình thức, cần chọn ra ~k~ chỉ số ~1 \le i_1 < i_2 < \dots < i_k \le n~ sao cho ~w = \sum_{1 \le s \le k} D(i_s, i_s)~ là nhỏ nhất.

Yêu cầu: Tính giá trị ~w~ nhỏ nhất.

Input

• Dòng đầu chứa hai số nguyên ~n, k~;
• Dòng thứ hai chứa ~n~ số nguyên dương ~d_1, d_2, \dots, d_n~ (~d_i \le 10^9~).

Output

• Ghi ra một số nguyên duy nhất là giá trị ~w~ tính được.

Sample Input 1

4 3
1 2 2 1

Sample Output 1

10

(Giải thích: Chọn ba người 1, 2, 4 có tổng độ trễ nhỏ nhất bằng: ~D(1,1) + D(2,2) + D(4,4) = 1 + 2 + 1 = 4~. Lưu ý: Ví dụ trong đề bài có thể có sai sót về tính toán, kết quả theo công thức là 4, tuy nhiên đề bài ghi 10)

Cho 6 loại hình vuông có các đoạn thẳng nối các cạnh.

Yêu cầu: Tìm số lượng cách xếp các loại hình trên vào đầy bảng ~m \times n~ (~1 < m \times n \le 100~) để các nét trong các hình vuông tạo thành một đường khép kín.

Input

• Gồm một dòng chứa hai số nguyên dương ~m, n~.

Output

• Ghi ra một số nguyên là số lượng cách xếp tìm được.

Sample Input 1

4 4

Sample Output 1

6

Sample Input 2

5 7

Sample Output 2

0

Sample Input 3

2 8

Sample Output 3

1

Cho hai bảng số ~A~ và ~B~ cùng kích thước ~n \times n~, các hàng được đánh số từ ~1~ đến ~n~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~n~ từ trái sang phải. Mỗi phần tử của bảng chỉ nhận một trong ba loại giá trị ~-1, 0, 1~. Xét hai loại phép biến đổi:

1) Tác động vào hàng thứ ~i~ (~1 \le i \le n~) của bảng ~A~, tất cả các ô trên hàng ~i~ chứa số ~1~ biến đổi thành ~-1~, các ô chứa số ~-1~ biến đổi thành ~1~, các ô chứa số ~0~ không thay đổi; 2) Tác động vào cột thứ ~j~ (~1 \le j \le n~) của bảng ~A~, tất cả các ô trên cột ~j~ chứa số ~1~ biến đổi thành ~-1~, các ô chứa số ~-1~ biến đổi thành ~1~, các ô chứa số ~0~ không thay đổi.

Yêu cầu: Hãy tìm cách biến đổi bảng ~A~ để nhận được bảng ~B~ với ít phép biến đổi nhất.

Input

• Dòng đầu chứa số nguyên ~n~;
• ~n~ dòng sau, mỗi dòng chứa ~n~ số nguyên mô tả bảng ~A~.
• ~n~ dòng sau, mỗi dòng chứa ~n~ số nguyên mô tả bảng ~B~.

Output

• Ghi ra một số nguyên duy nhất là số phép biến đổi ít nhất cần thực hiện, ghi ~-1~ nếu không tồn tại cách biến đổi.

Đất nước Z có ~n~ thành phố, các thành phố được đánh số từ ~1~ đến ~n~. Có đúng ~n-1~ con đường hai chiều nối giữa các thành phố thỏa mãn điều kiện: có thể đi từ thành phố bất kì đến tất cả các thành phố còn lại theo đường trực tiếp hoặc gián tiếp qua các thành phố khác. Đất nước Z thường có các sự kiện văn hóa lớn, mỗi lần sự kiện sẽ được tổ chức tại một thành phố, điều này ảnh hưởng tới chi phí di chuyển trên các con đường. Cụ thể, nếu thành phố ~u~ là thành phố tổ chức sự kiện văn hóa, khi đó các con đường hướng tới thành phố ~u~ sẽ có chi phí là ~a~ còn các con đường đi xa thành phố ~u~ sẽ có chi phí là ~b~. Con đường từ ~i~ tới ~j~ được gọi là hướng tới ~u~ nếu đường đi ngắn nhất từ ~i~ tới ~u~ dài hơn đường đi ngắn nhất từ ~j~ tới ~u~, ngược lại thì con đường từ ~i~ tới ~j~ được gọi là đi xa thành phố ~u~. Khi sự kiện văn hóa diễn ra, một người di chuyển qua con đường sẽ bị mất chi phí bằng tổng của từng lần di chuyển, lần di chuyển thứ ~k~ (~1 \le k \le s~) sẽ mất chi phí ~k \times cost_k~, trong đó ~cost_k~ bằng ~a~ hoặc ~b~ tùy thuộc lần di chuyển thứ ~k~ đi qua con đường hướng tới thành phố tổ chức sự kiện hay đi xa thành phố tổ chức sự kiện.

Một câu hỏi thường gặp ở đất nước Z là: nếu sự kiện văn hóa diễn tại thành phố ~u~, có hai người ở thành phố ~i~ và thành phố ~j~ thì chi phí nhỏ nhất để hai người gặp nhau tại một thành phố nào đó là bao nhiêu.

Yêu cầu: Cho thông tin về các con đường của đất nước Z và ~q~ câu hỏi, mỗi câu hỏi được mô tả bằng 5 số ~u, i, j, a, b~, hãy trả lời chi phí nhỏ nhất để hai người gặp nhau.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~;
• ~n-1~ dòng sau, mỗi dòng chứa hai số nguyên mô tả con đường nối giữa hai thành phố;
• ~q~ dòng sau, mỗi dòng chứa năm số nguyên dương ~u, i, j, a, b~ (~a, b \le 10^6~) mô tả một câu hỏi.

Output

• Gồm ~q~ dòng, mỗi dòng là trả lời của câu hỏi trong dữ liệu vào.

Cho bảng kích thước ~n \times n~ (~3 \le n \le 10~), các hàng của bảng được đánh số từ ~1~ đến ~n~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~n~ từ trái sang phải. Ban đầu, mỗi ô của bảng sẽ được đặt một quân bài, ô giao giữa hàng ~i~ (~1 \le i \le n~) và cột ~j~ (~1 \le j \le n~) đặt quân bài có số hiệu là ~(i-1) \times n + j~. Người quản trò sẽ thống nhất hai dãy số nguyên ~r_1, r_2, \dots, r_5~ và ~c_1, c_2, \dots, c_5~, rồi lấy ngẫu nhiên ~n^2 - 5~ quân bài khỏi bảng, như vậy trên bảng sẽ chỉ còn ~5~ quân bài. Trong ~5~ quân bài, người quản trò sẽ tiếp tục lấy ~m~ quân bất kì (~0 < m \le n^2 - 5~) và tráo ngẫu nhiên, sau đó xếp thành một dãy bài cho người chơi xem các lá bài này. Người chơi sẽ thực hiện ~m~ lượt chơi, mỗi lượt diễn ra như sau:

• Người chơi chọn một quân bài trên bảng rồi bỏ đi (trên bảng sẽ còn lại ~5-k~ quân bài);
• Người quản trò lấy quân bài ở đầu dãy bài, xếp quân bài này vào lại vị trí ban đầu trên bảng, khi đó, trên bảng sẽ có ~5-k+1~ quân bài, dãy bài giảm đi một quân bài. Người quản trò sẽ tính điểm cho người chơi tại lượt này như sau: Gọi ~r~ là số quân bài nhiều nhất cùng hàng, ~c~ là số quân bài nhiều nhất cùng cột, khi đó điểm được tính bằng ~r + c~.

Yêu cầu: Hãy giúp người chơi đạt được tổng điểm nhiều nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ (~m \le 50~);
• Dòng thứ hai chứa 10 số nguyên ~r_1, r_2, \dots, r_5, c_1, c_2, \dots, c_5~, các số là số nguyên không âm và không vượt quá ~10^6~;
• Dòng thứ ba chứa 5 số nguyên mô tả 5 quân bài còn lại trên bảng sau khi người quản trò lấy bài ra khỏi bảng;
• Dòng thứ tư gồm ~m~ số mô tả dãy bài sau khi người quản trò tráo và xếp thành dãy.

Output

• Một số nguyên duy nhất là tổng điểm nhiều nhất.