Nguồn: Học sinh Giỏi THPT Hà Nội năm 2016 - 2017

Cho dãy số \(A\) gồm \(n\) số hạng nguyên dương và hai số \(x, y\) nguyên dương. Dãy số \(U\) gồm \(m\) số hạng được cho bởi công thức \(u_1 = x; u_i = u_{i - 1} + y\) (\(1 < i \le m\)), trong đó số \(m\) được xác định để \(u_m\) nhỏ nhất, đồng thời \(u_m\) lớn hơn hoặc bằng giá trị lớn nhất của các số hạng trong dãy \(A\).

Yêu cầu: Hãy đếm xem trong dãy \(A\) có bao nhiêu số hạng vừa là số nguyên tố vừa là một số hạng nào đó trong dãy số \(U\).

Input

Dữ liệu vào từ tệp văn bản BAI1.INP:

• Dòng đầu chứa ba số nguyên dương \(n, x, y\) (\(1 < n \le 10^5, 1 \le x,y \le 100\));
• Dòng tiếp theo chứa \(n\) số nguyên dương của dãy \(A\), mỗi số không vượt quá \(10^6\).

Output

Kết quả ra tệp văn bản BAI1.OUT:

• Số lượng số hạng của dãy \(A\) thỏa mãn yêu cầu trên.

Examples

5 1 1
3 5 8 4 11

3

Note

• Dãy \(U\) gồm các số: \(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\)
• Dãy \(A\) có \(3\) số \(3, 5, 11\) là số nguyên tố và thuộc dãy \(U\).

Nguồn: Học sinh Giỏi THPT Hà Nội năm 2016 - 2017

Một công ty du lịch có \(n\) hướng dẫn viên du lịch tham gia hướng dẫn khách tham quan tại \(m\) địa điểm (các địa điểm được đánh số thứ tự từ \(1\) đến \(m\)). Vào một ngày nghỉ lễ, tại địa điểm thứ \(i\) (\(1 \le i \le m\)) có \(k_i\) khách tham quan. Tuy nhiên, tại địa điểm thứ \(i\), mỗi hướng dẫn viên chỉ có thể hướng dẫn cho không quá \(t_i\) khách tham quan.

Yêu cầu: Tìm phương án phân công các hướng dẫn viên tại các địa điểm sao cho số khách tham quan không được hướng dẫn là nhỏ nhất.

Input

Dữ liệu vào từ tệp văn bản BAI2.INP:

• Dòng đầu chứa hai số nguyên dương \(m\) và \(n\) (\(m \le 10^5, n \le 10^9\)).
• Trong \(m\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le m\)) chứa hai số nguyên dương \(k_i\) và \(t_i\), mỗi số không vượt quá \(10^9\).

Output

Kết quả ra tệp văn bản BAI2.OUT:

• Số lượng khách tham quan không được hướng dẫn nhỏ nhất.

Examples

3 3
4 2
10 7
1 1

3

Note

Có nhiều nhất \(12\) khách tham quan được hướng dẫn với phương án phân công các hướng dẫn viên như sau:

• Tại địa điểm \(1\) phân công \(1\) hướng dẫn viên.
• Tại địa điểm \(2\) phân công \(2\) hướng dẫn viên.
  Do đó số khách tham quan không được hướng dẫn nhỏ nhất là \(3\).

Nguồn: Học sinh Giỏi THPT Hà Nội năm 2016 - 2017

Để xác định nguyên nhân gây ra một số bệnh lạ, các nhà khoa học sử dụng kết quả xét nghiệm máu của \(n\) người được lưu tại \(n\) hồ sơ ở một bệnh viện. Để đối chứng, các nhà khoa học sử dụng hồ sơ xét nghiệm của cả người có bệnh và người không có bệnh. Các hồ sơ xét nghiệm được đánh số thứ tự từ \(1\) đến \(n\). Trong các hồ sơ xét nghiệm, có sự xuất hiện các virus thuộc \(m\) loại được đánh số thứ tự từ \(1\) đến \(m\). Mỗi bệnh do một loại virus gây ra. Các nhà khoa học mong muốn xếp mỗi loại virus vào một trong ba nhóm sau đây:

• Nhóm \(1\) bao gồm các virus không có khả năng gây ra bất kỳ bệnh nào. Các virus thuộc nhóm \(1\) là những virus xuất hiện trong ít nhất một hồ sơ xét nghiệm của người không có bệnh nào đó.
• Nhóm \(2\) bao gồm các virus có khả năng gây ra một bệnh nào đó.
• Nhóm \(3\) bao gồm các virus còn lại chưa thể xác định được có khả năng gây bệnh hay không.

Yêu cầu: Căn cứ kết quả xét nghiệm hiện có, cần phân loại các virus thành \(3\) nhóm như trên.

Input

Dữ liệu vào từ tệp văn bản BAI3.INP:

• Dòng đầu chứa hai số nguyên dương \(m\) và \(n\) (\(m \le 100, n ≤ 10^4\))
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le n\)) chứa \(m + 1\) số, trong đó \(t_1, t_2, ..., t_m\) nhận giá trị \(0\) hoặc \(1\) có ý nghĩa: Nếu \(t_j = 1\) thì virus thứ \(j\) xuất hiện trong hồ sơ thứ \(i\) và không xuất hiện nếu \(t_j = 0\); \(t_{m + 1} = 1\) nếu hồ sơ xét nghiệm là của người bị bệnh và \(t_{m + 1} = 0\) nếu hồ sơ xét nghiệm là của người không bị bệnh.

Output

Kết quả ra tệp văn bản BAI3.OUT:

• Dòng \(1\): Ghi số lượng các virus thuộc nhóm \(1\) và tiếp theo là chỉ số của các virus đó theo thứ tự tăng.
• Dòng \(2\): Ghi số lượng các virus thuộc nhóm \(2\) và tiếp theo là chỉ số của các virus đó theo thứ tự tăng.
• Dòng \(3\): Ghi số lượng các virus thuộc nhóm \(3\) và tiếp theo là chỉ số của các virus đó theo thứ tự tăng.

Examples

3 3
1 0 0 0
1 1 1 1
0 1 0 0

2 1 2
1 3
0

Note

Căn cứ \(3\) hồ sơ xét nghiệm:

• Có \(2\) virus thuộc nhóm \(1\) là các virus thứ \(1\) và thứ \(2\).
• Có \(1\) virus thuộc nhóm \(2\) là virus thứ \(3\).
• Không có virus nào thuộc nhóm \(3\).

Nguồn: Học sinh Giỏi THPT Hà Nội năm 2016 - 2017

Cho bảng số \(A\) gồm \(m\) dòng, \(n\) cột (các dòng được đánh số theo thứ tự từ \(1\) đến \(m\), các cột được đánh số theo thứ tự từ \(1\) đến \(n\)). Tại mỗi ô của bảng chứa một số nguyên dương trong hệ đếm nhị phân. Từ một ô \((i, j)\) bất kỳ thuộc dòng thứ \(i\), cột thứ \(j\) ta có thể đi đến một trong ba ô \((i + 1, j - 1)\) hoặc \((i + 1, j)\) hoặc \((i + 1, j + 1)\) (nếu các ô này nằm trong phạm vi của bảng).

Yêu cầu: Tìm đường đi từ một ô bất kỳ trên dòng đầu tiên của bảng, đến một ô nào đó ở dòng cuối cùng của bảng, sao cho tích các số của \(m\) ô thuộc đường đi này là lớn nhất.

Input

Dữ liệu vào từ tệp văn bản BAI4.INP:

• Dòng đầu chứa hai số nguyên dương \(m\), \(n\) (\(1 < m,n \le 200\));
• Trong \(m\) dòng tiếp theo, mỗi dòng chứa \(n\) số nhị phân của bảng A (mỗi số có độ dài tối đa không quá \(10\) chữ số).

Output

Kết quả ra tệp văn bản BAI4.OUT:

• Một số nhị phân duy nhất là tích các số theo yêu cầu trên.

Examples

3 3
11 10 1
10 11 1
1 10 11

11011

Note

• Đường đi qua các ô \((1, 1)\), \((2, 2)\) và \((3, 3)\) có tích \(11 \times 11 \times 11 = 11011\) là số lớn nhất.