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

Trong dịp Đại lễ 1000 năm Thăng Long-Hà Nội, An quan sát thấy nhiều đèn nhấp nháy được trang trí trên các đường phố. Vốn là một học sinh yêu thích môn Tin học và Vật lý, An quyết định tự tạo một dây đèn nhấp nháy đặc biệt. Dây đèn của An gồm \(n\) bóng nối tiếp nhau, đánh số thứ tự từ 1 đến \(n\) và được điều khiển theo nguyên tắc: Bắt đầu từ thời điểm \(0\) tất cả các bóng đèn đều ở trạng thái tắt, bóng thứ \(i\) sẽ lóe sáng vào các thời điểm \(t_i, 2t_i, 3t_i, ...\) (\(i = 1, 2, ..., n\)). An chờ đợi và muốn biết thời điểm nào mà cả \(n\) bóng đều cùng lóe sáng.

Ví dụ, nếu \(t_1 = 4\) thì tại các thời điểm \(4, 8, 12, 16, 20, ...\) bóng đèn \(1\) sẽ lóe sáng, \(t_2 = 6\) thì tại các thời điểm \(6, 12, 18, 24, 30, ...\) bóng đèn \(2\) sẽ lóe sáng. Như vậy, thời điểm \(12\) sẽ là thời điểm sớm nhất mà cả \(2\) bóng đèn đều cùng lóe sáng.

Yêu cầu: Cho \(t_1, t_2, ..., t_n\), hãy giúp An tính thời điểm sớm nhất mà tất cả \(n\) bóng đèn đều lóe sáng.

Input

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

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(2 \le n \le 30\)),
• Dòng thứ hai chứa \(n\) số nguyên dương \(t_1, t_2, ..., t_n\)(\(t_i \le 10^6\)).

Output

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

• Thời điểm sớm nhất mà tất cả \(n\) bóng đèn đều lóe sáng.

Examples

2
4 6

12

3
4 2 8
2 2

8

Note

• \(50\%\) số test ứng với \(50\%\) số điểm của bài toán có thời điểm sớm nhất tìm được không vượt quá \(10^9\)

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

Một xâu ký tự được gọi là mật khẩu "an toàn" nếu xâu có độ dài ít nhất bằng \(6\) và xâu chứa ít nhất một chữ cái in hoa \(('A'... 'Z')\), một chữ cái thường \(('a'... 'z')\), một chữ số \(('0'... '9')\).

Ví dụ: \(a1B2C3\), \(tinHoc6\) là hai mật khẩu "an toàn", còn \(a1B2C, a1b2c3, A1B2C3, tinHoc\) đều không phải là mật khẩu "an toàn".

Một lần, Bình nhìn thấy một xâu \(S\), chỉ gồm các loại ký tự: chữ cái in hoa, chữ cái thường và chữ số. Bình muốn tự kiểm tra khả năng đoán nhận mật khẩu bằng cách đếm xem có bao nhiêu cặp chỉ số \((i, j)\) thỏa mãn điều kiện: \(1 \le i < j \le length(S)\) và xâu con gồm các ký tự liên tiếp từ \(i\) đến \(j\) của \(S\) là mật khẩu "an toàn".

Yêu cầu: Cho xâu \(S\), tính số lượng cặp chỉ số \((i, j)\) thỏa mãn điều kiện nêu trên.

Input

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

• Gồm một dòng chứa xâu \(S\) có độ dài không quá \(10^6\).

Output

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

• Một số nguyên là số lượng cặp chỉ số \((i, j)\) tính được.

Examples

abc3456789PQ

6

abc123

0

Note

• \(50\%\) số test ứng với \(50\%\) số điểm của bài toán có độ dài xâu \(S\) không vượt quá \(1000\)

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

Cho một bàn cờ kích thước \(m \times n\) ô, các dòng được đánh số từ \(1\) đến \(m\) từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(n\) từ trái qua phải. Ô nằm ở vị trí dòng \(i\) và cột \(j\) của lưới được gọi là ô \((i, j)\) và khi đó, \(i\) được gọi là chỉ số dòng còn \(j\) được gọi là chỉ số cột của ô này. Được phép đặt một quân vua vào một ô của bàn cờ (mỗi ô đặt không quá một quân), khi đó nó có thể khống chế \(8\) ô lân cận xung quanh (\(8\) ô được đánh số từ \(1\) đến \(8\), xem hình vẽ dưới đây).

Trên bàn cờ đã đặt trước một số quân vua (không có \(2\) quân vua nào khống chế nhau), người ta muốn đặt thêm nhiều nhất các quân vua lên bàn cờ mà vẫn bảo đảm không có \(2\) quân vua nào khống chế nhau.

Yêu cầu: Cho biết các ô đã đặt quân vua, hãy đặt thêm nhiều nhất quân vua lên bàn cờ sao cho trên bàn cờ không có \(2\) quân nào khống chế nhau.

Input

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

• Dòng đầu tiên chứa \(3\) số nguyên \(m, n, k\) (\(0 < m, n \le 30; 0 \le k \le m \times n\)), trong đó \(m, n\) là kích thước bàn cờ, \(k\) là số quân vua đã được đặt trên bàn cờ.
• Dòng thứ \(i\) trong \(k\) dòng tiếp theo gồm \(2\) số \(a_i, b_i\) là chỉ số dòng và chỉ số cột của ô thứ \(i\) đã có quân vua.

Output

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

• Một dòng duy nhất ghi số nguyên \(s\) là số lượng nhiều nhất quân vua được đặt thêm lên bàn cờ.

Examples

2 3 0

2

2 2
```
???+ success "Output"

0

Note

• Cho biết trước \(3\) test trong \(10\) test sẽ dùng để chấm (xem trong bảng dưới đây).