Cho số nguyên dương ~n~. Hãy tìm số nguyên dương ~a~ sao cho ~a + (a+1) + (a+2) + (a + 3) = n~.

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

• Một dòng gồm duy nhất số nguyên dương ~n~ (~1 \le n \le 10^9~).

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

• In ra số nguyên dương ~a~. Nếu không tồn tại số nguyên dương ~a~ thỏa mãn, in ra NO.

Example

Sample Input 1

10

Sample Output 1

1

Sample Input 2

11

Sample Output 2

NO

Tuấn có một chuỗi ký tự chỉ gồm các chữ cái thường tiếng Anh và đang cố mã hóa chuỗi này theo một mã hóa nhất định.

Mã hóa này được mô tả bởi hai chuỗi ~A~ và ~B~, trong đó mỗi ký tự ở chuỗi ~A~ được ánh xạ tới một ký tự tương ứng trong chuỗi ~B~. Ví dụ, nếu

• ~A = ~ abcdefghijklmnopqrstuvwxyz
• ~B = ~ zyxwvutsrqponmlkjihgfedcba,

thì a sẽ được ánh xạ thành z, b sẽ thành y, ....

Việc biến đổi chuỗi chỉ một lần thì khá nhàm chán, vì vậy, với một số nguyên dương ~K~, Tuấn muốn lặp lại quá trình mã hóa này ~K~ lần. Nhưng giờ đây Tuấn đã mệt và nhờ bạn giúp đỡ. Bạn có thể giúp Tuấn để có được chuỗi cuối cùng không?

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

• Dòng đầu tiên chứa xâu ~S \ (1 \leq |S| \leq 10^5)~ chỉ gồm các kí tự La-tinh in thường.
• Dòng tiếp theo chứa một số nguyên dương ~K \ (1 \leq K \leq 10^9)~.
• Hai dòng tiếp theo, mỗi dòng chứa lần lượt hai xâu ~A~ và ~B~ có đúng ~26~ kí tự là hoán vị của các kí tự La-tinh in thường từ a đến z.

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

• In ra một xâu duy nhất là kết quả bài toán.

Scoring

• Subtask 1 (~30 \%~ số điểm): ~K = 1~.
• Subtask 2 (~30 \%~ số điểm): ~K, |S| \leq 2000~.
• Subtask 3 (~20 \%~ số điểm): ~K \leq 10^5~.
• Subtask 4 (~20 \%~ số điểm): Không có ràng buộc gì thêm.

Sample Input

hnoi
2
abcdefghijklmnopqrstuvwxyz
pnudzgabijkyehlrqxfmsctovw

Sample Output

nbyi

Giải thích: Các kí tự của xâu hnoi được mã hóa như sau:

• h → b → n
• n → h → b
• o → l → y
• i → i → i

Cho một dãy số nguyên dương gồm n phần tử ~a_1, a_2, \ldots, a_n~. Trọng số ~W~ của dãy ~a~ được định nghĩa là ước chung lớn nhất của tất cả các phần tử trong dãy, tức là ~W = \gcd(a_1, a_2, \ldots, a_n)~.

Ở đây, ~gcd~ được định nghĩa là phép lấy ước chung lớn nhất.

Bạn được phép thay đổi tối đa hai phần tử bất kỳ trong dãy ~a~ thành hai số nguyên dương khác sao cho trọng số mới của dãy đạt giá trị lớn nhất có thể.

Nhiệm vụ của bạn là tìm giá trị lớn nhất có thể của trọng số mới.

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

• Dòng đầu tiên gồm số nguyên dương ~n~ (~3 \le n \le 2 \cdot 10^5~).
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~).

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

• Gồm số nguyên dương duy nhất là giá trị lớn nhất có thể của trọng số mới sau khi thay đổi tối đa hai phần tử trong dãy ~a~.

Scoring

• Subtask ~1~ (~30\%~ số điểm): ~N = 3~.
• Subtask ~2~ (~30\%~ số điểm): ~N, a_i \le 1000~.
• Subtask ~3~ (~30\%~ số điểm): ~N, a_i \le 10^5~.
• Subtask ~4~ (~10\%~ số điểm): Không có ràng buộc gì thêm.

Example

Sample Input 1

3
4 4 12

Sample Output 1

12

Sample Input 2

5
6 1 9 2 12

Sample Output 2

3

Explanation

Ở ví dụ thứ nhất, ta thay hai phần tử ~a_1~ và ~a_2~ thành giá trị ~12~.

Ở ví dụ thứ hai, ta thay hai phần tử ~a_2~ và ~a_4~ thành giá trị ~3~.

Aaron đang chơi một trò chơi video có tên là Escape!. Trò chơi diễn ra trên một lưới có ~N~ hàng và ~M~ cột:

• Các hàng được đánh số từ ~1, 2, \dots, N~ từ trên xuống.
• Các cột được đánh số từ ~1, 2, \dots, M~ từ trái sang phải.
• Ô ở hàng ~i~ và cột ~j~ được ký hiệu là ~(i, j)~.

Hai ô khác nhau được coi là kề nhau nếu chúng có chung một cạnh (tối đa 4 ô kề nhau cho mỗi ô). Cụ thể:

• Ô ~(i, j)~ kề với ~(i-1, j)~, ~(i+1, j)~, ~(i, j-1)~, và ~(i, j+1)~ nếu các ô đó tồn tại.

Mỗi ô trên lưới thuộc một trong bốn loại dưới đây, và được biểu diễn bởi một ký tự:

• .: Ô trống.
• d: Ô có quái vật.
• e: Ô cửa thoát hiểm.
• #: Ô tường.
• Nếu một ô ban đầu chứa quái vật thì sau khi quái vật đó rời đi, ô đó là ô trống. Điều tương tự xảy ra với người chơi.

Aaron muốn an toàn đến được cửa thoát hiểm. Ban đầu, Aaron có 2 HP (tượng trưng cho ~2~ máu) và bắt đầu ở một ô không phải tường. Mỗi giây, các sự kiện sau diễn ra theo thứ tự:

1. Nếu HP của Aaron ~\leq 0~, trò chơi kết thúc và Aaron thua ngay lập tức.
2. Nếu Aaron đang ở ô cửa thoát hiểm (và HP ~\geq 1~), trò chơi kết thúc và Aaron thắng ngay lập tức.
3. Aaron có thể chọn đứng yên hoặc di chuyển đến một ô kề không phải tường.
4. Sau đó, mỗi quái vật sẽ có thể chọn đứng yên hoặc di chuyển đến một ô kề không phải tường. Nhiều quái vật có thể di chuyển đến cùng một ô.
5. Cuối cùng:
   • Mỗi quái vật ở cùng ô với Aaron sẽ tấn công Aaron, giảm HP của Aaron đi ~1~. Sau đó, quái vật đó biến mất khỏi lưới.

Yêu cầu

Trước khi bắt đầu trò chơi, do mạng quá lag, Aaron phải quyết định trước chuỗi các ô sẽ di chuyển tới. Nói cách khác, Aaron cần cố định các bước đi của mình mà không biết trước chuyển động của các quái vật. Do đó, các quái vật có thể xem kế hoạch của Aaron và di chuyển theo kế hoạch đó.

Một ô được gọi là ô lợi thế nếu và chỉ nếu:

• Nó không phải là tường.
• Nếu Aaron bắt đầu ở ô đó, di chuyển theo kế hoạch của mình, và luôn thắng bất kể cách di chuyển của các quái vật.

Nhiệm vụ của bạn là tính số lượng ô lợi thế trên lưới.

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

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ (~1 \leq N, M \leq 3000~).
• Tiếp theo là ~N~ dòng, mỗi dòng gồm ~M~ ký tự mô tả các ô trên lưới:
  • Ký tự thứ ~j~ trong dòng thứ ~i~ biểu diễn loại của ô ~(i, j)~.

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

In ra một số nguyên duy nhất: số lượng ô lợi thế.

Scoring

• Subtask 1 (~15\%~ số điểm): Chỉ có tối đa 1 quái vật trên lưới.
• Subtask 2 (~15\%~ số điểm): ~N = 1~.
• Subtask 3 (~10\%~ số điểm): ~N, M \leq 10~.
• Subtask 4 (~20\%~ số điểm): ~N, M \leq 40~.
• Subtask 5 (~10\%~ số điểm): Chỉ có tối đa 1 cửa thoát hiểm.
• Subtask 6 (~20\%~ số điểm): ~N, M \leq 2000~.
• Subtask 7 (~10\%~ số điểm): Không có ràng buộc thêm.

Example

Sample Input 1

4 5
...d.
.e#e.
..d#d
.e.d.

Sample Output 1

14

Sample Input 2

4 3
e.e
##.
.#.
.#d

Sample Output 2

6

Explanation

Sample 1

Giả sử chúng ta bắt đầu tại ô (4,5) và lộ trình được chọn như sau:

...d. 
.e#e. 
..d#d 
.XXXX

X biểu thị lộ trình đã chọn.

Với lộ trình này, quái vật tại (4,4) đứng yên và quái vật tại (3,3) di chuyển xuống ngay sau khi người chơi thực hiện bước đầu tiên.

Trước khi trò chơi bắt đầu, người chơi có 2 HP và đang ở vị trí (4,5).

...d. 
.e#e. 
..d#d 
.e.dP

P biểu thị vị trí của người chơi.

Bây giờ, người chơi di chuyển sang trái, đến ô (4,4). Tại đây có một quái vật, nên người chơi chỉ còn 1 HP. Đồng thời, quái vật tại (3,3) di chuyển xuống và lưới bây giờ như sau:

...d. 
.e#e. 
...#d 
.edP.

Rõ ràng, người chơi sẽ thua ngay tại bước tiếp theo, ngay sau khi di chuyển sang trái. Có thể thấy rằng ô (4,5) không phải là ô lợi thế sau khi xem xét tất cả các khả năng của lộ trình.

Sample 2

Do chỉ có một quái vật trên bản đồ, chỉ cần xuất phát từ bất kì ô nào đi tới được lối thoát hiểm là Aaron có thể thoát ra.

Bạn được cho hai mảng có độ dài ~n~ .

• Phần tử thứ ~i~ của mảng thứ nhất là ~a_i~ .
• Phần tử thứ ~i~ của mảng thứ hai là ~b_i~ .

Một cách chia cả hai mảng thành các mảng con không rỗng được gọi là tốt nếu thỏa mãn các điều kiện sau:

• Mỗi phần tử thuộc đúng một mảng con duy nhất.
• Số lượng mảng con của cả hai mảng bằng nhau, tức là nếu mảng thứ nhất được chia thành đúng ~k~ mảng con, thì mảng thứ hai cũng phải được chia thành đúng ~k~ mảng con.
• Với mọi ~1 \leq i \leq k~, trung bình cộng của mảng con thứ ~i~ bên trái mảng thứ nhất phải nhỏ hơn hoặc bằng trung bình cộng của mảng con thứ ~i~ bên trái mảng thứ hai.

Yêu cầu: Tính số cách để chia cả hai mảng thành các mảng con không rỗng thỏa mãn các điều kiện trên. Kết quả phải được chia dư với ~10^9 + 7~. Hai cách được xem là khác nhau nếu số lượng mảng con khác nhau hoặc nếu một phần tử thuộc về mảng con khác nhau.

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

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \leq n \leq 500)~.
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \leq a_i \leq 10^6)~.
• DDòng cuối cùng chứa ~N~ số nguyên ~b_1, b_2, \dots, b_n~ ~(1 \leq b_i \leq 10^6)~.

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

• In ra số cách chia mảng thỏa mãn các điều kiện, chia dư với ~10^9 + 7~.

Scoring

• Subtask ~1~ (~20\%~ số điểm): ~n \le 10~
• Subtask ~2~ (~30\%~ số điểm): ~n \le 80~
• Subtask ~3~ (~30\%~ số điểm): ~n \le 300~
• Subtask ~4~ (~20\%~ số điểm): Không giới hạn gì thêm.

Example

Sample Input 1

3
1 3 2
2 2 2

Sample Output 1

3

Note

Ba cách hợp lệ là:

• Chia mảng thứ nhất thành ~[1, 3], [2]~ và mảng thứ hai thành ~[2, 2], [2]~.
• Chia mảng thứ nhất thành ~[1, 3], [2]~ và mảng thứ hai thành ~[2], [2, 2]~.
• Chia mảng thứ nhất thành ~[1, 3, 2]~ và mảng thứ hai thành ~[2, 2, 2]~.