lqdoj004

Cảm thấy quá mệt mỏi với việc nghỉ dịch Covid-19 ở nhà, Doraemon rủ Nobita và những người bạn đi phiêu lưu ở hòn đảo kho báu ở Mỹ cách đây 1500 năm. Sau khi đến đảo, vì quá mệt mỏi sau chuyến hành trình dài, mọi người quyết định nghỉ chân một lúc. Tại đây, Doraemon chợt nhớ ra việc học hành bết bát của Nobita nên đã đố Nobita một câu hỏi để ôn lại các thuật toán khủng như Suffix Array, Treap, Palindrome Tree, etc…

Doraemon cho Nobita 1 chiếc hộp đặc biệt biết cứ bỏ \(M\) quả chuối vào chiếc hộp này thì tất cả quả chuối sẽ biến mất. Sau đó Doraemon cho Nobita 2 số \(L\) và \(R\) và bắt Nobita phải chọn 2 số \(i\) và \(j\) \((i < j)\) trong đoạn \(L\) và \(R\). Sau khi chọn Nobita sẽ có được tổng số chuối là \(i \times j\). Tiếp theo, cậu sẽ phải liên tục bỏ \(M\) quả chuối vào thùng đến khi số chuối còn lại ít hơn \(M\). Vì Nobita là 1 cậu bé “ngốc nghếch” nên cậu muốn biết được số lượng chuối còn lại ít nhất sau khi bỏ vào thùng.

Input

• Một dòng duy nhất, gồm ba số lần lượt là \(L, R, M\) \((1 \leq L < R \leq 2000, 1 \leq M \leq 2000)\).

Output

• Một dòng duy nhất, là kết quả của bài toán.

Scoring

• Ở bản dễ, \(1 \leq L < R \leq 2000\).
• Ở bản khó, \(1 \leq L < R \leq 10^9\).

Example

4 7 13 

2

Trong lúc Doraemon và những người bạn vẫn còn vui vẻ dưới ánh nắng tươi vàng trong một tiết trời hè nóng nực bên bãi biển tươi xanh thơm ngát mùi muối và những cánh chim trên cao bay dập dờn, dập dờn báo hiệu một mùa thu sắp đến và kết thúc một chuỗi ngày hè nóng nực nhưng cực kì đẹp đẽ và vui tươi thì ở phía bên kia xa xăm của hòn đảo tươi đẹp, dưới những tán cây dừa, một đàn khỉ nhí nhố gồm \(N\) chú đang háo hức xách cặp đến trường để đón lễ khai giảng nửa năm học mới 2019,5 - 2020.

Nhưng đâu phải chú nào cũng có tốc độ ngang nhau nên có chú đến sớm và có chú đến muộn và không có chú nào đến cùng thời điểm. Biết rằng khi chú thứ \(i\) đến thì có \(A_i\) chú khỉ khác có mặt trong lớp (tính cả chú thứ \(i\)). Hiệu trưởng kiêm giáo viên chủ nhiệm đã nhờ bác bảo vệ xây dựng lại thứ tự đến trường của các chú khỉ để có biện pháp xử lí thích đáng với những chú khỉ đi trễ.

Input

• Dòng đầu tiên chứa một số \(N\) là sĩ số của lớp \((1 \leq N \le 10^6)\)
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa một số duy nhất \(A_i\) \((1\leq A_i \leq N)\).

Output

• Một dòng duy nhất gồm \(N\) số, số thứ \(i\) là thứ tự đến trường của các chú khỉ \(i\).

Example

6
5 4 2 1 6 3 

4 3 6 2 1 5

Quay trở lại với Doraemon và đồng bọn, sau khi nghỉ ngơi thoải mái, cả bọn bắt đầu chuyến hành trình khám phá hòn đảo. Trong lúc đi tham quan, Suneo bỗng phát hiện được một phế tích bỏ hoang và thông báo cho cả bọn cùng khám phá nơi này vì có vẻ nó là nơi bắt đầu của cuộc hành trình tìm kiếm kho báu. Vừa bước chân vào phế tích, cửa ra liền đóng sầm lại làm cả bọn sợ hãi và trước mặt họ có vẻ là một câu đố. Một bức tranh có kích thước \(N×M\) hiện lên trước mặt họ, các ô bên trong bức tranh đều có màu trắng và viền của bức tranh có màu xám. Bên cạnh bức tranh có vài dòng chữ: “Ta sẽ vẽ vào bức tranh này dùng những con quái vật. Ta sẽ sắp xếp một số quái vật ở viền ngoài của bức tranh và hướng mặt về phía bảng. Việc sắp xếp các con quái vật có thể được biểu diễn bởi \(4\) chuỗi \(A, B, C, D\):

• Nếu \(A_i = 1\), có \(1\) con quái vật ở vị trí \((i, 0)\) \((1 \le i \le N)\).
• Nếu \(B_i = 1\), có \(1\) con quái vật ở vị trí \((i, M + 1)\) \((1 \le i \le N)\).
• Nếu \(C_i = 1\), có \(1\) con quái vật ở vị trí \((0, i)\) \((1 \le i \le M)\).
• Nếu \(D_i = 1\), có \(1\) con quái vật ở vị trí \((N + 1, i)\) \((1 \le i \le M)\).

2 quái vật bất kì sẽ tô 2 màu khác nhau, và màu của mỗi quái vật đều khác trắng và xám. Lần lượt thực hiện các thao tác sau đến khi tất cả quái vật để đã được chọn:

• Chọn \(1\) quái vật bất kì.
• Quái vật sẽ liên tục thực hiện thao tác sau nếu như ô trước mặt nó là \(1\) ô trắng: Đi sang ô trước mặt và tô màu ô đó với màu của nó. Nếu ô trước mặt nó có màu ko phải màu trắng thì quái vật sẽ dừng lại. May mắn cho các ngươi, lần này 2 chuỗi C và D đều không có quái vật.

Các ngươi hãy cho biết có bao nhiêu trạng thái khác nhau của bức tranh \((\)mod \(10^9 + 7)\). Hai trạng thái được coi là khác nhau nếu ở trạng thái này có ít nhất 1 ô khác màu với trạng thái kia."

Vì quá bất ngờ và sợ hãi, cả bọn chả biết phải làm gì để vượt qua thử thách này nên nhờ các bạn giúp họ vượt qua thử thách để cả bọn có thể bình tĩnh lại.

Input

• Dòng đầu tiên chứa hai số \(N, M\) \((1 \le N, M \le 10^5)\) là số hàng và số cột của bức tranh.
• \(4\) dòng tiếp theo, Mỗi dòng chứa \(1\) chuỗi lần lượt là \(A, B, C, D\).

Output

• Gồm 1 dòng chứa số nguyên là kết quả của bài toán.

Example

4 5
1110
1100
00000
00000 

4

![][1]

![][2]

![][3]

![][4]

![][5]

Cảm thấy quá mệt mỏi với việc nghỉ dịch Covid-19 ở nhà, Doraemon rủ Nobita và những người bạn đi phiêu lưu ở hòn đảo kho báu ở Mỹ cách đây 1500 năm. Sau khi đến đảo, vì quá mệt mỏi sau chuyến hành trình dài, mọi người quyết định nghỉ chân một lúc. Tại đây, Doraemon chợt nhớ ra việc học hành bết bát của Nobita nên đã đố Nobita một câu hỏi để ôn lại các thuật toán khủng như Suffix Array, Treap, Palindrome Tree, etc…

Doraemon cho Nobita 1 chiếc hộp đặc biệt biết cứ bỏ \(M\) quả chuối vào chiếc hộp này thì tất cả quả chuối sẽ biến mất. Sau đó Doraemon cho Nobita 2 số \(L\) và \(R\) và bắt Nobita phải chọn 2 số \(i\) và \(j\) \((i < j)\) trong đoạn \(L\) và \(R\). Sau khi chọn Nobita sẽ có được tổng số chuối là \(i \times j\). Tiếp theo, cậu sẽ phải liên tục bỏ \(M\) quả chuối vào thùng đến khi số chuối còn lại ít hơn \(M\). Vì Nobita là 1 cậu bé “ngốc nghếch” nên cậu muốn biết được số lượng chuối còn lại ít nhất sau khi bỏ vào thùng.

Input

• Một dòng duy nhất, gồm ba số lần lượt là \(L, R, M\) \((1 \leq L < R \leq 10^9, 1 \leq M \leq 2000)\).

Output

• Một dòng duy nhất, là kết quả của bài toán.

Scoring

• Ở bản dễ, \(1 \leq L < R \leq 2000\).
• Ở bản khó, \(1 \leq L < R \leq 10^9\).

Example

4 7 13 

2

Hôm nay Nobita phải đi học bù từ sáng tới khuya cho kì nghỉ dịch Covid-19 dài kỷ lục 😢. Doraemon ở nhà một mình cả ngày quá cô đơn nên nó đã bày ra trò mới - Lật Bánh Rán. Doraemon đã mua sẵn 64 cái bánh rán đặc biệt của thế kỉ 22. Mỗi khi lật mặt bánh thì cả màu và vị bên trong đều thay đổi 😮. Có 2 loại bánh khác nhau : màu nâu và màu trắng. Doraemon sẽ chơi với một con robot AI. Mèo ta và robot sẽ thay phiên nhau đi. Doraemon luôn đặt những chiếc bánh rán màu nâu xuống bàn cờ khi chơi lượt của mình, còn robot thì ngược lại (đặt bánh màu trắng). Doraemon sẽ đi trước.

Bàn cờ là một bàn ăn vuông vức được chia thành \(8\) hàng và \(8\) cột (tức là \(64\) ô vuông nhỏ): các hàng được đánh số từ \(1\) tới \(8\) theo chiều từ trên xuống dưới, các cột được đánh các chữ cái từ \(a\) tới \(h\) theo chiều từ trái sang phải.

Đây là 1 ví dụ của bàn cờ:

Tới lượt một người chơi, người đó phải đặt bánh rán theo màu của mình tại một ô trống sao cho nó liền kề với một dãy các bánh rán khác màu (theo đường chéo hoặc hàng ngang, hàng dọc) và ở đầu kia của dãy bánh khác màu ấy là một bánh rán cùng màu với bánh mà người chơi này vừa đặt xuống. Nói cách khác, chiếc bánh rán người chơi này mới đặt xuống cùng với một chiếc bánh rán cũ (cùng màu) bất kì kẹp ngay 2 đầu của một dãy các bánh rán khác màu.

Trong hình trên, những ô có vòng tròn viền đỏ là những vị trí mà Doraemon có thể đặt bánh xuống. Mỗi khi người chơi đặt bánh xuống như vậy, tất cả những bánh rán khác màu ở giữa sẽ được lật lại và đổi thành bánh cùng loại với chiếc bánh rán mới được đặt xuống. (Việc lật bánh để đổi loại được thực hiện bởi bàn cờ - máy lật bánh rán tự động từ thế kỉ 23 😮)

Hiện tại là lượt chơi của Doraemon, nhưng vì vừa chơi vừa nhìn những chiếc bánh rán thơm ngon đổi màu nãy giờ nên mèo ta đã hoa mắt, đói xỉu 😢 và không thể nhìn ra được nước đi tối ưu có thể lật lên nhiều chiếc bánh rán màu nâu nhất (Doraemon chỉ thích vị của những bánh màu nâu). Bạn hãy giúp chú mèo máy tội nghiệp này nhé! Hãy in ra vị trí mà Doraemon nên đặt bánh rán xuống.

Trong hình trên, 2 hình tròn màu đỏ là ô đặt bánh rán tối ưu nhất.

Input

• Gồm 8 dòng chứa các xâu độ dài 8 chỉ gồm các kí tự \(B\), \(W\) và \(.\) mô tả bàn cờ. Những ô có bánh rán đang có màu nâu ở mặt ngửa biểu thị bởi chữ cái \(B\), bánh rán có màu trắng là chữ \(W\), còn lại là dấu chấm.

Output

• Gồm một tọa độ duy nhất là vị trí bạn sẽ đặt bánh rán xuống (VD: \(a1\), \(h8\), …) và số lượng bánh rán nâu sẽ lật lên được (2 thông tin ngăn nhau bởi dấu cách).

Example

.WWWWWB.
........
...WWB..
.WWWB...
B.B.B...
........
....BWB.
........ 

a1 5

In ra c3 5 cũng được coi là đáp án đúng.

Lưu ý

Nếu có nhiều tọa độ cùng lật được số lượng bánh rán nâu lớn nhất, bạn có thể in ra một tọa độ bất kì.

Nếu bánh rán mà Doraemon vừa đặt xuống “kẹp” được nhiều dãy bánh rán khác màu khác nhau thì nó có thể lật hết số bánh rán khác màu trong tất cả các dãy đó!

Doraemon quên mất, phải giới thiệu tới các bạn.

Á chết, có một con virus Maisu(Mice) đang hoành hành trong não của Doraemon! Chết, đã sợ chuột, nay còn bị virus Maisu thì Mon 2k(112) đi đời rồi ông giáo à 🙁 Đã vậy, Doraemon còn gặp lại 7 người anh em của mình, rồi biệt đội Doramini nữa, và lại lây con virus này tới những homie của mình. Thật là xui xẻo.

May mắn thay, vẫn còn một cách để cứu sống Doraemon và những người bạn. Virus Maisu sử dụng thuật toán AS(M)R để mã hóa toàn bộ dữ liệu trong não của cậu. Với mỗi con chồn, thuật toán mã hóa sử dụng một mật mã \(M \leq 10^9\). Để giải mã, chúng ta cần tìm ba khóa \(x, y, z\) \((1 \leq x, y, z \leq 2^{60} )\) , sao cho \(x⊕y⊕z=0\), và cả \(x,y\) và \(z\) đều chia hết cho số \(M\). Ở đây \(⊕\) là phép toán thao tác bit XOR.

Nobita với sự trợ giúp của vợ mình là Jaiko, á lộn Shizuka, đã tìm ra một vài số \(M\). Việc của bạn là tìm ra ba ba khóa \(x, y ,z\) bất kỳ để mở khóa và giải mã dữ liệu trong đầu Doraemon hậu đậu.

Các bạn hãy giúp Nô để tương lai Nô không bị Jaian bắt nạt, dẫn tới việc bị cưới Jaiko nhé!

Fact không có thật: Jaiko tương lai ốm nhom và xinh hơn cả Shizuka.

Input

• Dòng thứ nhất chứa một số \(T\) \((1 \leq T \le 10^5)\) là số lượng khóa đã tìm ra.
• Với \(T\) dòng tiếp theo, dòng thứ \(i\) \((1 \leq i \leq T)\) chứa một số \(M_i\) \((1 \leq M_i \leq 10^9)\) là mật mã của chú chồn thứ \(i\).

Output

• Gồm \(T\) dòng, dòng thứ \(i\) \((1 \leq i \leq T)\) chứa ba số \(x_i, y_i, z_i\) \((1 \leq x_i, y_i, z_i < 2^{60})\) là ba khóa dùng để giải mã chú chồn thứ \(i\).

Example

1
5 

80 90 10

Quay trở lại với Doraemon và đồng bọn, sau khi nghỉ ngơi thoải mái, cả bọn bắt đầu chuyến hành trình khám phá hòn đảo. Trong lúc đi tham quan, Suneo bỗng phát hiện được một phế tích bỏ hoang và thông báo cho cả bọn cùng khám phá nơi này vì có vẻ nó là nơi bắt đầu của cuộc hành trình tìm kiếm kho báu. Vừa bước chân vào phế tích, cửa ra liền đóng sầm lại làm cả bọn sợ hãi và trước mặt họ có vẻ là một câu đố. Một bức tranh có kích thước \(N×M\) hiện lên trước mặt họ, các ô bên trong bức tranh đều có màu trắng và viền của bức tranh có màu xám. Bên cạnh bức tranh có vài dòng chữ: “Ta sẽ vẽ vào bức tranh này dùng những con quái vật. Ta sẽ sắp xếp một số quái vật ở viền ngoài của bức tranh và hướng mặt về phía bảng. Việc sắp xếp các con quái vật có thể được biểu diễn bởi \(4\) chuỗi \(A, B, C, D\):

• Nếu \(A_i = 1\), có \(1\) con quái vật ở vị trí \((i, 0)\) \((1 \le i \le N)\).
• Nếu \(B_i = 1\), có \(1\) con quái vật ở vị trí \((i, M + 1)\) \((1 \le i \le N)\).
• Nếu \(C_i = 1\), có \(1\) con quái vật ở vị trí \((0, i)\) \((1 \le i \le M)\).
• Nếu \(D_i = 1\), có \(1\) con quái vật ở vị trí \((N + 1, i)\) \((1 \le i \le M)\).

2 quái vật bất kì sẽ tô 2 màu khác nhau, và màu của mỗi quái vật đều khác trắng và xám. Lần lượt thực hiện các thao tác sau đến khi tất cả quái vật để đã được chọn:

• Chọn \(1\) quái vật bất kì.
• Quái vật sẽ liên tục thực hiện thao tác sau nếu như ô trước mặt nó là \(1\) ô trắng: Đi sang ô trước mặt và tô màu ô đó với màu của nó. Nếu ô trước mặt nó có màu ko phải màu trắng thì quái vật sẽ dừng lại. May mắn cho các ngươi, lần này 2 chuỗi B và D đều không có quái vật.

Các ngươi hãy cho biết có bao nhiêu trạng thái khác nhau của bức tranh \((\)mod \(10^9 + 7)\). Hai trạng thái được coi là khác nhau nếu ở trạng thái này có ít nhất 1 ô khác màu với trạng thái kia."

Vì quá bất ngờ và sợ hãi, cả bọn chả biết phải làm gì để vượt qua thử thách này nên nhờ các bạn giúp họ vượt qua thử thách để cả bọn có thể bình tĩnh lại.

Input

• Dòng đầu tiên chứa hai số \(N, M\) \((1 \le N, M \le 10^5)\) là số hàng và số cột của bức tranh.
• \(4\) dòng tiếp theo, Mỗi dòng chứa \(1\) chuỗi lần lượt là \(A, B, C, D\).

Output

• Gồm 1 dòng chứa số nguyên là kết quả của bài toán.

Example

4 5
1100
0000
01001
00000 

6