Có ~M~ nhiệm vụ. Nhiệm vụ thứ ~i~ có:

• thời gian thực hiện ~x_i~
• độ khó ~y_i~

Nếu hoàn thành nhiệm vụ này, ta nhận được tiền thưởng:

~500 \times x_i + 2 \times y_i~

Có ~N~ máy. Máy thứ ~j~ có khả năng:

• làm việc tối đa trong ~T_j~ đơn vị thời gian
• xử lí nhiệm vụ có độ khó không vượt quá ~D_j~

Một máy có thể thực hiện nhiệm vụ ~i~ nếu:

• ~x_i \le T_j~
• ~y_i \le D_j~

Quy tắc

• Mỗi máy chỉ được làm nhiều nhất một nhiệm vụ.
• Mỗi nhiệm vụ chỉ được giao cho nhiều nhất một máy.

Yêu cầu

Hãy phân công nhiệm vụ cho các máy sao cho tổng tiền thưởng thu được là lớn nhất.

Input

• Dòng đầu chứa hai số nguyên ~M, N~.
• Dòng thứ hai chứa ~2M~ số nguyên: ~x_1, y_1, x_2, y_2, \ldots, x_M, y_M~.
• Dòng thứ ba chứa ~2N~ số nguyên: ~T_1, D_1, T_2, D_2, \ldots, T_N, D_N~.

Output

In ra một số nguyên duy nhất là tổng tiền thưởng lớn nhất có thể đạt được.

Ràng buộc

• ~1 \le M, N \le 10^5~
• ~1 \le x_i \le 1440~
• ~1 \le y_i \le 200~
• ~1 \le T_j \le 1440~
• ~1 \le D_j \le 200~

Subtasks

• Subtask 1 (40%): ~M, N \le 20~
• Subtask 2 (30%): ~M, N \le 100~
• Subtask 3 (30%): Không có ràng buộc bổ sung.

Input

3 3
60 50 90 120 30 80
60 100 90 130 30 90

Output

90500

Cho số nguyên không âm ~A~.

Ta thực hiện phép biến đổi lặp lại như sau: Ở mỗi bước, lấy số hiện tại nhân với chữ số tận cùng của nó.

Yêu cầu

Cho số nguyên ~N~, hãy thực hiện phép biến đổi trên ~N~ lần và in ra chữ số tận cùng của số thu được.

Input

Gồm một dòng chứa hai số nguyên ~A~ và ~N~.

Output

In ra chữ số tận cùng sau ~N~ lần biến đổi.

Ràng buộc

• ~0 \le A \le 10^{18}~
• ~0 \le N \le 10^{18}~

Subtasks

• Subtask 1 (40%): ~A, N \le 10~
• Subtask 2 (40%): ~N \le 10^6~
• Subtask 3 (20%): Không có ràng buộc bổ sung.

Ví dụ

Input

7 3

Output

1

Giải thích

• Bước 1: ~7 \times 7 = 49~
• Bước 2: ~49 \times 9 = 441~
• Bước 3: ~441 \times 1 = 441~

Chữ số tận cùng là ~1~.

Cho dãy số nguyên dương ~A~ gồm ~N~ phần tử ~A_1, A_2, \ldots, A_N~.

Với mỗi phần tử ~A_i~, ta xét tất cả các ước số dương của ~A_i~ và thêm chúng vào một dãy mới ~D~.
Lưu ý rằng nếu một ước số xuất hiện nhiều lần (từ các phần tử khác nhau), thì nó cũng được thêm vào ~D~ tương ứng số lần đó.

Sau khi xử lí tất cả các phần tử, ta thu được dãy ~D~.
Tiếp theo, sắp xếp dãy ~D~ theo thứ tự không giảm.

Yêu cầu

Cho ~Q~ truy vấn. Mỗi truy vấn gồm một số nguyên dương ~x~.
Với mỗi truy vấn, hãy tìm phần tử thứ ~x~ trong dãy ~D~ sau khi đã sắp xếp.

Input

• Dòng đầu tiên chứa hai số nguyên ~N, Q~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~x~.

Output

In ra ~Q~ dòng, mỗi dòng là giá trị ~D[x]~ tương ứng với truy vấn.

Ràng buộc

• ~1 \le N \le 10^6~
• ~1 \le Q \le 10^5~
• ~1 \le A_i \le 10^6~
• ~1 \le x \le |D|~

Subtasks

• Subtask 1 (20%): ~N, Q, A_i \le 2000~
• Subtask 2 (20%): Tất cả ~A_i~ là số nguyên tố
• Subtask 3 (20%): ~N \le 10^4~, và mọi truy vấn có ~x \le 2 \times 10^6~
• Subtask 4 (20%): Mọi truy vấn có ~x \le 2 \times 10^6~
• Subtask 5 (20%): Không có ràng buộc bổ sung

Ví dụ

Input

3 4
3 6 2
1
3
6
8

Output

1
1
3
6

Giải thích

• ~3 \to 1, 3~
• ~6 \to 1, 2, 3, 6~
• ~2 \to 1, 2~

Dãy ~D~: ~[1,3,1,2,3,6,1,2]~

Sắp xếp: ~[1,1,1,2,2,3,3,6]~

• ~x=1 \to 1~
• ~x=3 \to 1~
• ~x=6 \to 3~
• ~x=8 \to 6~

Cho một mảng ~A~ gồm ~N~ phần tử ~a_1, a_2, \ldots, a_N~. Có ~Q~ truy vấn cần thực hiện, mỗi truy vấn thuộc một trong hai loại sau:

• Truy vấn loại 1: Cú pháp ~1\ l\ x~, nhân tất cả các phần tử từ vị trí ~l~ đến ~N~ (tức là ~a_i~ với ~l \le i \le N~) với số nguyên ~x~.
• Truy vấn loại 2: Cú pháp ~2\ p\ y~, cộng thêm số nguyên ~y~ vào phần tử ~a_p~.

Yêu cầu

Sau khi thực hiện tất cả ~Q~ truy vấn, hãy in ra giá trị của các phần tử trong mảng ~A~. Do kết quả có thể rất lớn, hãy in ra phần dư của mỗi phần tử khi chia cho ~10^9 + 7~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~Q~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \ldots, a_N~ là các phần tử ban đầu của mảng ~A~.
• ~Q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn có dạng ~1\ l\ x~ hoặc ~2\ p\ y~.

Output

In ra ~N~ số nguyên trên một dòng, cách nhau bởi khoảng trắng, là giá trị của các phần tử ~a_1, a_2, \ldots, a_N~ sau khi thực hiện các phép tính và chia lấy dư cho ~10^9 + 7~.

Ràng buộc

• ~1 \le N, Q \le 10^6~
• ~|a_i| \le 10^9~
• ~1 \le l, p \le N~
• ~|x|, |y| \le 10^9~

Subtasks

• Subtask 1 (30%): ~N, Q \le 5000~
• Subtask 2 (30%): Các truy vấn loại ~1~ luôn có ~l = 1~
• Subtask 3 (20%): ~N, Q \le 10^5~
• Subtask 4 (20%): Không có ràng buộc gì thêm.

Ví dụ

Input

5 4
1 2 3 4 5
2 3 10
1 2 2
2 5 -3
1 4 3

Output

1 4 26 24 21

Giải thích

Ban đầu: ~[1, 2, 3, 4, 5]~

• Sau truy vấn ~2\ 3\ 10~: ~[1, 2, 13, 4, 5]~
• Sau truy vấn ~1\ 2\ 2~: ~[1, 4, 26, 8, 10]~
• Sau truy vấn ~2\ 5\ (-3)~: ~[1, 4, 26, 8, 7]~
• Sau truy vấn ~1\ 4\ 3~: ~[1, 4, 26, 24, 21]~

```

Cho bảng kích thước ~k \times n~, các hàng được đánh số từ ~1~ đến ~k~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~n~ từ trái sang phải. Ô nằm ở hàng ~i~ và cột ~j~ ~\left(1 \le i \le k,\ 1 \le j \le n\right)~ gọi là ô ~(i, j)~.

Mỗi ô điền một số sao cho mỗi hàng là một hoán vị của ~1, 2, \ldots, n~. Gọi ~s_j~ là tổng ~k~ số trên cột ~j~.

Một bảng được gọi là đẹp nếu ~s_1, s_2, \ldots, s_n~ là một dãy số tự nhiên liên tiếp tăng dần, nghĩa là:

~s_j = s_{j-1} + 1 \quad \text{với mọi } 2 \le j \le n~.

Yêu cầu

Bạn được thực hiện không quá ~10^6~ phép đổi chỗ hai ô trên cùng một hàng. Hãy tìm một cách biến đổi để nhận được một bảng đẹp.

Input

• Dòng đầu chứa hai số nguyên dương ~k, n~.
• ~k~ dòng tiếp theo, dòng thứ ~i~ chứa ~n~ số nguyên là một hoán vị của ~1, 2, \ldots, n~.

Output

• Dòng đầu chứa số nguyên ~t~ là số thao tác đổi chỗ, hoặc ghi ~-1~ nếu không thể biến đổi để nhận được bảng đẹp.
• Nếu biến đổi được, tiếp theo là ~t~ dòng, mỗi dòng chứa ba số ~i, j_1, j_2~ cho biết đổi chỗ hai số ở hai ô ~(i, j_1)~, ~(i, j_2)~.

Ràng buộc

• ~1 \le k \le 5~
• ~1 \le n \le 10^5~

Subtasks

• Subtask 1 (30%): ~k = 1,\ n \le 100~
• Subtask 2 (30%): ~k = 2,\ n \le 10~
• Subtask 3 (20%): ~n \le 100~
• Subtask 4 (20%): Không có ràng buộc nào thêm.

Ví dụ 1

Input

1 3
1 3 2

Output

1
1 2 3

Giải thích

Sau khi đổi chỗ hai phần tử ở cột ~2~ và ~3~ của hàng ~1~, ta được bảng:

~[1\ 2\ 3]~

Khi đó các tổng cột là ~1, 2, 3~, tạo thành một dãy liên tiếp tăng dần.

Ví dụ 2

Input

2 2
1 2
1 2

Output

-1

Giải thích

Không tồn tại cách biến đổi để nhận được một bảng đẹp.

Ví dụ 3

Input

2 3
1 2 3
1 2 3

Output

2
1 2 3
2 1 2

Giải thích

Sau hai phép đổi chỗ trên, ta nhận được bảng:

• Hàng 1: ~[1\ 3\ 2]~
• Hàng 2: ~[2\ 1\ 3]~

Khi đó các tổng cột là ~3, 4, 5~, là một dãy số liên tiếp tăng dần.

Các nhà khoa học cần khôi phục một thông điệp mật mã được khắc trên một chiếc vòng cổ.

Thông điệp là một xâu ~S~ chỉ gồm các kí tự từ 'a' đến 'z'. Vì xâu nằm trên một vòng tròn nên kí tự cuối cùng của xâu được coi là đứng liền trước kí tự đầu tiên.

Thông tin hiện có là ~N~ mảnh xâu, mỗi mảnh xâu là một đoạn con gồm các kí tự liên tiếp xuất hiện trên chiếc vòng cổ. Việc khôi phục thực sự khó khăn vì các nhà khoa học không biết chính xác vị trí của các mảnh xâu trên xâu ~S~, có thể có rất nhiều xâu khác nhau chứa ~N~ mảnh xâu như vậy.

Tuy nhiên, các nhà khoa học nhận định rằng ~S~ càng ngắn mà mọi mảnh xâu trong số ~N~ mảnh đều xuất hiện trên đó (dưới dạng đoạn con liên tiếp của vòng tròn) thì càng đáng tin cậy.

Yêu cầu

Cho ~N~ mảnh xâu, hãy tìm một xâu ~S~ có độ dài càng ngắn càng tốt sao cho mỗi mảnh xâu trong ~N~ mảnh đều xuất hiện dưới dạng đoạn con liên tiếp trên xâu vòng tròn ~S~.

Input

• Dòng đầu chứa số nguyên dương ~N~.
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa một mảnh xâu là một xâu gồm các chữ cái thường, có độ dài không quá ~10~.

Output

• Gồm một dòng chứa xâu ~S~ tìm được.

Ràng buộc

• ~1 \le N \le 500~
• Mỗi mảnh xâu có độ dài không quá ~10~
• Các kí tự đều là chữ cái thường 'a' đến 'z'

Chấm điểm

Bài có nhiều output đúng, vì vậy cần dùng custom checker.

Với mỗi test:

• Gọi ~P~ là độ dài xâu do thí sinh in ra.
• Gọi ~J~ là độ dài xâu của ban giám khảo.

Nếu xâu của thí sinh không hợp lệ thì được ~0~ điểm ở test đó.

Nếu hợp lệ thì số điểm nhận được ở test đó là:

~\min\left(1,\ \dfrac{J^{20}}{P^{20}}\right)~

Như vậy:

• nếu ~P \le J~ thì được tối đa điểm của test đó;
• nếu ~P > J~ thì vẫn có thể được điểm thành phần.

Subtasks

• Subtask 1 (25 điểm): ~N \le 10~
• Subtask 2 (25 điểm): ~N \le 20~
• Subtask 3 (25 điểm): ~N \le 50~
• Subtask 4 (25 điểm): ~N \le 500~

Ví dụ

Input

3
ab
ba
aa

Output

aba

Giải thích

Xâu vòng tròn ~aba~ chứa cả ba mảnh:

• ~ab~
• ~ba~
• ~aa~ (đi qua vị trí cuối và đầu của vòng tròn)