Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 100

FireGhost130104 đang sinh test cho Bedao Regular Contest 12! Trong quá trình sinh test, anh ấy đánh số các file tăng dần từ ~1, 2, 3, ...~. Tuy nhiên, khi lưu trên máy tính, các file test sẽ được sắp xếp theo thứ tự tên của chúng, vì thế, nếu bài có trên ~10~ test, chúng sẽ bị sắp xếp sai thứ tự (ví dụ, test ~10~ sẽ đứng trước test ~2~).

Để giải quyết vấn đề này, FireGhost130104 thêm một số số ~0~ vào trước tên mỗi file, sao cho số lượng số 0 được sử dụng là ít nhất và sau khi thêm, độ dài tên các file đều bằng nhau. Ví dụ, khi bài có ~10~ test, anh ấy sẽ lưu tên các file lần lượt là ~01, 02, 03, 04, 05, 06, 07, 08, 09, 10~.

Tuy nhiên, trong quá trình upload bài, một số lượng lớn test đã bị mất, chỉ còn lại ~n~ file. Từ tên các file chưa bị mất, FireGhost130104 muốn biết: số lượng test tối thiểu và tối đa của bài này là bao nhiêu?

Input

Dòng đầu tiên gồm số nguyên dương ~n~ (~1 \le n \le 1000~) - số lượng test chưa bị mất.

Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa tên các file chưa bị mất. Dữ liệu đảm bảo tên các file này có độ dài bằng nhau và không vượt quá ~9~.

Output

In ra hai số nguyên dương: số lượng test tối thiểu và tối đa của bài toán.

Sample Input 1

3
4
7
2

Sample Output 1

7
9

Sample Input 2

3
07
10
03

Sample Output 2

10
99

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 100

Lam_lai_cuoc_doi là một người cầu kì và khó tính; anh luôn cẩn thận trong từng lời ăn tiếng nói, kể cả trong việc nhắn tin. Để tiện liên lạc trong lúc khẩn cấp; anh đã tạo ra mật mã huynh đệ và đưa cho những người anh em thân thiết của mình học thuộc. Mật mã huynh đệ mà Lam_lai_cuoc_doi sáng tạo ra có nguyên lí giống như mã Morse, nhưng thay vì sử dụng các dấu chấm và dấu gạch, "ngôn ngữ" này lại sử dụng các emoji.

Trong "từ điển" của Lam_lai_cuoc_doi15 loại emoji: ;-), ;-(, :), :(, :-\, :-P, :D, :C, :-0, :-|, 8-0, :-E, :-X, :∼(, [:|||:]. Trong lúc khẩn cấp, anh ấy đã tạo ra mật mã để gửi đến tất cả anh em. Tuy nhiên, chất lượng mạng kém đã làm thông tin anh gửi đi bị lẫn lộn và không thể phân biệt được thứ tự.

Là một người thông minh, FireGhost130104 có thể ngay lập tức sắp xếp lại các kí tự để phục hồi tin nhắn hoàn chỉnh; nhưng kazamahoang thì không như vậy, anh hiện đang rất cần sự giúp đỡ để có thể hiểu được tin nhắn của Lam_lai_cuoc_doi.

Input

Một dòng duy nhất chứa một xâu kí tự có độ dài không quá ~10^5~ mô tả tin nhắn mà kazamahoang nhận được.

Output

In ra nhiều dòng, mỗi dòng chứa một emoji xuất hiện trong tin nhắn lúc đầu. Dữ liệu đảm bảo tồn tại ít nhất một cách để khôi phục tin nhắn.

Sample Input 1

|:|;[|)-:]

Sample Output 1

[:|||:]
;-)

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 100

Nhân dịp Black Friday, lastPledge quyết định mua một món quà để tặng crush. Món quà là một dãy số ~a~ gồm ~n~ phần tử, tuy nhiên, vì đây là hàng sale off nên chất lượng không được tốt lắm. Vì vậy, lastPledge muốn tự tay chỉnh sửa lại món quà.

lastPledge sẽ thực hiện thao tác sau vô số lần. Ở lần thứ ~i~, anh ấy sẽ tăng giá trị của ~a_{p_i}~ thêm ~x_i~. Tuy nhiên, vì một số lý do kĩ thuật, ~x_i \ge x_{i - 1}~ với mọi ~i > 0~.

Một dãy số được gọi là dễ thương nếu bất kì dãy con liên tiếp độ dài ~k~ nào của nó đều có tổng chia hết cho ~2~. Vì không muốn thay đổi món quà ban đầu quá nhiều, lastPledge muốn thực hiện ít thao tác nhất có thể để dãy số ban đầu trở nên dễ thương.

Hãy giúp lastPledge chuẩn bị món quà dễ thương nhất để tặng cho crush nhé!

Input

Dòng đầu tiên gồm ~2~ số nguyên dương ~n~ - độ dài dãy ~a~ và ~k~ ~(k \leq n \leq 10^6)~.

Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ thể hiện các phần tử của dãy ~a~ (~0 \le a_i \le 10^9~).

Output

Một dòng duy nhất chứa đáp án của bài toán: số lượng thao tác ít nhất để làm dãy ~a~ trở nên dễ thương.

Sample Input 1

5 3
1 10 1 2 9

Sample Output 1

2

Notes

Ở test ví dụ trên, ta có thể làm dãy ~a = [1, 10, 1, 2, 9]~ trở nên dễ thương trong ~2~ thao tác:

  • Ở lượt thứ 1: ta chọn ~p_1 = 4~ và ~x_1 = 3~. Lúc này, ~a = [1, 10, 1, 5, 9]~.
  • Ở lượt thứ 2: ta chọn ~p_2 = 5~ và ~x_2 = 7~. Lúc này, ~a = [1, 10, 1, 5, 16]~.

Sau ~2~ thao tác, tất cả các dãy con liên tiếp độ dài ~3~ đều có tổng chia hết cho ~2~.


Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 100

Hôm nay, trong lúc tham quan thư viện thành phố, FireGhost130104 bỗng tìm thấy cuốn sách "300 bài code thiếu nhi" nằm gọn một góc, không ai chú ý tới. Anh ấy hiếu kì, lật ra xem ngay bài đầu tiên:

Cho dãy số nguyên ~a~ và dãy nhị phân ~b~ gồm ~n~ phần tử. Cho một hoán vị ~p~ độ dài ~n~, ta sẽ xây dựng dãy ~c~ như sau:

  • Đặt ~v_i = b_{p_1} \oplus b_{p_2} \oplus \ldots \oplus b_{p_i}~.

  • Nếu ~v_i = 1~, ~c_i = a_{p_i}~; ngược lại, ~c_i = -a_{p_i}~.

Hãy in ra mảng ~c~ sau khi thực hiện các thao tác trên.

"Chậc, bài gì mà dễ thế nhỉ" – FireGhost130104 thầm nghĩ. Với sở thích tăng độ khó cho mọi thứ, chỉ một lúc sau, anh ấy đã nghĩ ra phiên bản khó hơn:

Cho hai dãy ~a~ và ~b~ gồm ~n~ phần tử, hãy đếm số hoán vị ~p~ thỏa mãn: ~\sum_{i = 1}^{n} c_i \vdots k~.

Vì kết quả có thể rất lớn, hãy in ra kết quả theo modulo ~10^9 + 7~.

Input

Dòng đầu tiên gồm hai số nguyên dương ~n~ (~1 \le n \le 500~) và ~k~ (~1 \le k \le 500~).

Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~0 \le a_i \le 10^9~).

Dòng thứ ba gồm ~n~ số nguyên ~b_1, b_2, ..., b_n~ (~0 \le b_i \le 1~).

Output

In ra số hoán vị thỏa mãn đề bài theo modulo ~10^9 + 7~.

Scoring

  • ~10\%~ số test thoả mãn ~n \le 10~.

  • ~90\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

4 9
2 5 5 1
1 0 1 0

Sample Output 1

8

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 100

Một xâu được gọi là xâu đối xứng (xâu palindrome) nếu xâu đó không thay đổi khi viết theo chiều xuôi (từ trái sang phải) hay chiều ngược (từ phải sang trái). Trong tất cả các xâu đối xứng, một xâu sẽ được gọi là siêu đối xứng nếu các kí tự của chúng ở vị trí chẵn bằng nhau.

Yêu cầu: từ xâu ~s~ cho trước, hãy đếm số lượng xâu con liên tiếp là xâu siêu đối xứng.

Input

  • Dòng đầu tiên gồm số nguyên ~n~ ~(1 \le n \le 2 \cdot 10^5)~ - độ dài của xâu ~s~.

  • Dòng thứ hai gồm xâu ~s~ có độ dài ~n~, các kí tự trong xâu ~s~ là các kí tự tiếng Anh in thường.

Output

  • In ra số lượng xâu con liên tiếp siêu đối xứng của xâu ~s~.

Scoring

  • ~30\%~ số test thoả mãn ~n \le 500~.

  • ~30\%~ số test khác thoả mãn ~n \le 5000~.

  • ~40\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

5
abcba

Sample Output 1

7

Notes

Trong test ví dụ trên, các xâu con liên tiếp siêu đối xứng là ~[1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [2, 4], [1, 5]~.


Giới hạn thời gian: 3.0s / Giới hạn bộ nhớ: 256M

Điểm: 100

Nhân dịp ngày lễ quốc tế FA, nhà vua xứ Bedao muốn thúc đẩy chỉ số hạnh phúc của quốc gia nên đã tổ chức một sự kiện ghép đôi thú vị. Có ~n~ người ế lâu năm, nổi tiếng khắp mạng xã hội đã được mời tham gia (trong đó có kazamahoang).

Bản đồ quốc gia có thể quy về hệ tọa độ ~Oxy~, trong đó người thứ ~i~ đang đứng ở vị trí ~(x_i, y_i)~. Trong một đơn vị thời gian, người đứng ở vị trí ~(u, v)~ có thể di chuyển đến các vị trí ~(u + 1, v - 1)~, ~(u + 1, v)~, ~(u + 1, v + 1)~, ~(u, v + 1)~, ~(u - 1, v + 1)~, ~(u - 1, v)~, ~(u - 1, v - 1)~, ~(u, v - 1)~. Để được phát người yêu, tất cả người chơi phải di chuyển đến nơi tổ chức sự kiện đặt ở vị trí ~(a, b)~. Vì tất cả mọi người đều rất nôn nóng có gấu để ôm, mỗi người sẽ di chuyển theo lộ trình nhanh nhất đến nơi tổ chức sự kiện.

Tuy nhiên, đất nước này có ~m~ vùng đất bị nguyền rủa, vùng đất thứ ~j~ sẽ bao phủ một hình chữ nhật có tọa độ góc trái dưới ~(c_j, d_j)~ và tọa độ góc phải trên ~(e_j, f_j)~. Theo truyền thuyết, tất cả các cặp đôi yêu nhau khi đến đây đều không có kết cục tốt đẹp (tất nhiên, lời nguyền này không ảnh hưởng đến những người ế, vì vậy những người tham gia sự kiện có thể đi qua vùng đất này một cách bình thường). Vì thế, nhà vua không muốn tổ chức sự kiện trong những vùng đất này.

Nhà vua muốn chọn vị trí tổ chức sự kiện ~(a, b)~ sao cho thời điểm đầu tiên mà tất cả ~n~ người tập trung là sớm nhất. Hãy giúp nhà vua nhé!

Input

  • Dòng đầu tiên gồm hai số nguyên dương ~n, m~ ~(n \le 10^5, m \le 5 \cdot 10^4)~ - số người tham gia sự kiện và số vùng đất bị nguyền rủa.

  • Dòng thứ ~i~ trong ~n~ dòng tiếp theo gồm hai số nguyên ~x_i, y_i~ (~0 \le x_i, y_i \le 10^9~) - toạ độ hiện tại của người thứ ~i~.

  • Dòng thứ ~j~ trong ~m~ dòng tiếp theo chứa bốn số nguyên ~c_j, d_j, e_j, f_j~ (~0 \le c_j \le e_j \le 10^9, 0 \le d_j \le f_j \le 10^9~) - toạ độ góc trái dưới và phải trên của vùng đất nguyền rủa thứ ~j~.

Output

  • In ra thời điểm sớm nhất mà sự kiện có thể bắt đầu.

Scoring

  • ~10\%~ số test thoả mãn ~m = 1~.

  • ~20\%~ số test khác thoả mãn ~m \le 18~.

  • ~20\%~ số test khác thoả mãn ~m \le 300~.

  • ~50\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

3

Notes