10^6, 10^7 và những người bạn Div 2

Sau khi hú vía mới qua được cảnh ngàn cân treo sợi tóc ấy, Tấn đã thành công đưa team chiếm giải kk và mới được ba tặng con Robot siêu cấp có cục pin siêu khủng. Tấn hằng ngày vẫn lấy nó ra chơi. Cho đến \(1\) ngày, Tấn đọc được bài viết về Tỉ Lệ Vàng, Tấn mới nghĩ ra một trò chơi mới.

Tấn lôi cái bàn cờ vô hạn của mình ra, và đánh dấu \(T\) khu vực hình chữ nhật, khu thứ \(i\) có \(2\) cạnh lần lượt là \(X_i\) và \(Y_i\). Với mỗi khu thứ \(i\), Tấn đặt con Robot lên ô trái trên của khu vực ấy, đặt \(1\) cây bút màu mà cậu dùng để đánh dấu khu vực xuống phía dưới con Robot cho nó vạch đường đi, rồi chơi như sau: Hướng góc nhìn của cả con Robot về hướng bên tay phải, rồi cho nó di chuyển liên tục. Nếu như ô nó dự định đi tới (hoặc \(1\) cạnh kề ô đó) bị vẽ màu thì nó sẽ dừng lại, nó sẽ quay \(90^o\) về phía tay phải (so với góc nhìn của con robot) rồi đi tiếp. Cho đến \(1\) ô nào đó mà nó quay đủ \(360^o\) mà không thể tìm thấy đường đi hợp lệ thì nó sẽ dừng lại và báo hiệu cho Tấn biết số hiệu của ô nó dừng lại:

Các ô được đánh số như thế này trong khu vực \(8x8\). Robot sẽ từ ô số \(1\) qua ô số \(8\) (hàng số màu cam), rồi từ đó đi đến ô số \(64\) (hàng số màu xanh nhạt), rồi từ đó đi tiếp đến ô \(57\) (hàng số màu tím), rồi tới ô số \(9\) (hàng số màu xanh đậm), rồi tiếp tục quay rồi đi tiếp tới ô \(15\) (hàng số màu hường), rồi đi tiếp… cho đến ô số \(36\) (ô in đậm) thì Robot không tìm thấy đường đi nên nó sẽ dừng.

Cậu ghi lại ô dừng của Robot trong \(T\) trường hợp, rồi đem cho Tài xem. Mỗi tội sau đó Tấn lại lỡ tay làm rách tờ giấy nên kết quả cậu ghi lại đều bị mất hết, may thay vẫn còn các giá trị \(X_i\) và \(Y_i\) của \(T\) khu vực ấy, nên ít nhất cậu cũng hy vọng có thể khôi phục lại kết quả. Các bạn ơi, hãy giúp Tấn tìm ra các kết quả bị mất nhé!

Input:

• Dòng 1 gồm số \(T≤10^6;\)
• \(T\) dòng sau, mỗi dòng thứ \(i\) có \(2\) số \(X_i\) và \(Y_i\) \(X_i,Y_i≤10^8.\)

Output:

• Với mỗi dòng thứ i, in ra theo đề yêu cầu (kèm chữ “Test #” với chỉ số của câu hỏi (i).

Scoring:

• 20% số test có \(X_i,Y_i ≤ 10^2.\)
• 50% số test có \(X_i,Y_i ≤ 10^5.\)

Example

Một số \(n\) bất kì luôn có \(1\) tập ước số không chứa \(1\) riêng của nó, dù là số nguyên tố hay hợp số. Ví dụ như số \(6\) có tập ước số không chứa \(1\) là \((2;3;6)\), còn số \(420\) có tập ước số không chứa \(1\) là \((2;3;4;5;6;7;10;12;14;15;20;21;28;35;60;84;105;140;210;420)\). Trinh mới học thêm về số nguyên tố và hợp số, liền về nhà lấy giấy ra viết \(1\) số \(420\) và dãy ước không chứa \(1\) của chính số \(420\) ấy. Viết xong rồi, cậu nhìn lại thì thắc mắc: Ủa? Sao có nhiều đoạn số liên tiếp thế này? Có đoạn có tới \(6\) số liên tiếp lận? (Nếu bạn thắc mắc là đoạn nào, thì đó là đoạn \((2;3;4;5;6;7)\) đấy) Rồi cô nghĩ tiếp: Thế nếu mình muốn tạo ra \(1\) số \(n\) bất kì mà trong dãy ước ấy có ít nhất \(1\) đoạn liên tiếp có \(k\) số thì làm thế nào nhỉ? Cô bí bài này nên cô muốn nhờ các bạn ở LQDOJ rằng: Cho \(1\) số tự nhiên \(k(k≤10^6)\), hãy tìm số nguyên dương \(n\) bé nhất có thể mà trong dãy ước số không chứa \(1\) của nó có ít nhất \(1\) đoạn số liên tiếp có chiều dài không nhỏ hơn \(k\).

Input

• Dòng \(1\) nhập số \(q\) chỉ số truy vấn\((q<=100)\), sau đó là \(q\) dòng, mỗi dòng nhập duy nhất \(1\) số \(k\)

Output

• Mỗi truy vấn xuất kết quả mod cho \(10^9+7\).

Example

1
2

6

Ràng buộc: 50% test có \(k<=100\)

Fibonacci là một dãy số huyền bí được phát minh ra từ xa xưa, là nghiệm của \(1\) bài toán ít người biết đến trong bộ sách … gì gì đó ko nhớ nữa :))) . Những con số đầu tiên của dãy là \((1;1;2;3;5;8; ...)\). Trinh rất thích dãy số này, và thường xuyên cho Tấn xem những gì cô mới chơi đùa được với dãy số ấy. Tấn cũng đã học về dãy số ấy và phát hiện nó có một điều gì đó rất bất bình thường. Sau một hồi khám phá, cuối cùng mọi thứ được đúc kết trong câu đố của cậu cho Trinh:

Cho \(T\) số \(n\). Với mỗi số \(n\), tìm tổng các ước số của số Fibonacci thứ \(n\) mà nó là số Fibonacci, sao cho các ước không được trùng nhau (\(2\) số \(1\) đầu dãy được tính làm \(1\)).

Trinh, dù thích câu đố này, nhưng không thể làm nó vì cô đang bận xem bóng đá Vòng Loại thứ \(3\) World Cup khu vực Châu Á (hay ít nhất là cô nói với cậu thế). Trinh nhờ các bạn giải giúp câu đố này.

Nhưng mọi chuyện vẫn chưa kết thúc tại đây. Tấn còn ác hơn khi cho các số \(n\) của cậu ẩn trong \(1\) xâu kí tự \(S\), trong đó các số \(n\) được bao giữa các dấu ngoặc tròn “( )”, và số \(T\) của cậu bị ẩn và bạn sẽ chẳng biết được số \(T\) này. Mục đích của việc này là làm cho các bạn loạn mắt lên thôi chứ chẳng có gì cả :))) Trinh “trả giá” độ khó bài này vì các bạn và cuối cùng Tấn chỉ cho thêm \(1\) cái điều kiện “giảm bớt” là: Các cặp ngoặc không lồng vào nhau, chúng độc lập với nhau và không tác động lên các cặp ngoặc kia. Trinh đành chấp nhận thử thách của cậu và nhờ các bạn. Các bạn hãy giúp Trinh nhé 🙁 Các kết quả của cùng 1 số n in ra mỗi kết quả mỗi dòng.

Input

• Gồm \(1\) dòng duy nhất là xâu \(S\), chứa \(T\) số \(n\) (\(T\) ẩn và \(T≤100\) cùng với các \(n≤10^{12}\)).

Output

• Với mỗi số \(n\), mỗi dòng in \(1\) kết quả là tổng các ước số của số Fibonacci thứ n mà nó là số Fibonacci sau khi mod \(10^9+7\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n≤10^3.\)
• Subtask \(2\) (\(25\%\) số điểm): \(n≤10^6.\)
• Subtask \(3\) (\(25\%\) số điểm): \(n≤10^9.\)
• Subtask \(4\) (\(25\%\) số điểm): \(n≤10^{12}.\)

Example

12345(15)12345

618

Mọi thứ nào đó luôn tồn tại \(2\) mặt đối lập nhau. Đó là \(2\) mặt “sự thích” và “sự ghét”. Dù Tấn và Trinh ghét cực ghét những cảnh máu đổ trong Squid Game, nhưng Tấn và Trinh thích Squid Game ở chỗ: Những trò chơi đó đã được nâng cấp từ những trò chơi dân gian Hàn Quốc rất đỗi bình thường. Thế là \(2\) bạn lại lôi cái bàn cờ vua \(n * n\) của Tấn ra (\(n\le 1000\)), mỗi ô được đánh số là \(i\) có tọa độ (\(x_i,y_i\)) thay vì chỉ bằng phẳng thì được chồng lên ai hộp lập phương có cùng kích thước với kích thước ô (\(a_i>0\)):

Các ô được đánh số như thế này trong bàn cờ 8x8.

Chơi với cái bàn cờ “kì dị” này riết cũng chán, Tấn đem con Robot nhỏ siêu hiện đại ở nhà ra. Nó hiện đang có 300V trong cái hộp pin siêu cấp của mình và nó cứ mỗi giây chỉ tiêu tốn 0,00001V nếu di chuyển. Tấn đặt nó trên ô số \(1\) và đưa ra một số \(T\), yêu cầu rằng Trinh phải điều khiển Robot đến ô có số \(n^2\) trong thời gian không quá T giây. Biết:

• Robot chỉ có thể di chuyển đến ô lân cận ở bên phải, bên dưới và ô có góc phải dưới, không thể di chuyển đến các ô lân cận khác.
• Tấn muốn ô nào Trinh có thể đi chéo thi hãy đi chéo, không được đi khác đi.
• Robot di chuyển đến ô lân cận ở bên phải, bên dưới và ô có góc phải dưới tốn [1s*((chênh lệch chiều cao giữa 2 ô) +1)] (nếu ô đó cao hơn hoặc bằng phẳng với ô đang đứng, tức là leo lên ô bên cạnh).
• Robot di chuyển đến ô lân cận ở bên phải, bên dưới và ô có góc phải dưới tốn [1s+0,01s*(chênh lệch chiều cao giữa 2 ô)] (nếu ô đó thấp hơn ô đang đứng, tức là rớt xuống ô bên cạnh).
• Robot rất bền để có thể chịu được bất kì chấn động nào (có lẽ trừ động đất). Nhưng yên tâm đi, nhà Tấn không bao giờ có động đất đâu :)))))

VD:

Trong hình này, ví dụ như Robot đang đứng ở ô viền đỏ có màu xanh (có số 2):

• Nếu Robot đi sang ô màu xanh (cũng có số \(2\)) phía dưới thi sẽ tốn \(1s\) di chuyển qua.
• Nếu Robot đi sang ô màu vàng (có số \(1\)) bên phải thì sẽ tốn \(1s + 0.01s = 1.01s\) vì ô vàng có độ cao thấp hơn ô đang đứng là \(1\).
• Nếu Robot đi sang ô màu cam (có số \(3\)) ở bên phải và phía dưới thì sẽ tốn \(1s + 1s = 2s\) vì ô cam có độ cao cao hơn ô đang đứng là \(1\).

Trinh đang đau đầu vì … chỉ đơn giản là đang ăn sáng nên không có thời gian chơi trò này :))). các bạn hãy giúp Trinh biết rằng: Nếu có thể hướng Robot đến ô có số \(n^2\) thì hãy in ra thứ tự của các ô cần di chuyển (kể cả ô kết thúc và ô bắt đầu) tối ưu nhất, còn không hãy in ra từ “Can’t solve”.

Input

• Dòng \(1\) gồm \(2\) số là \(n\) và \(T\);
• \(n\) dòng tiếp theo, mỗi dòng gồm có \(n\) số nguyên \(a\).

Output

• Ghi ra lộ trình đi của Robot, giữa 2 chỉ số có 1 dấu '->' hoặc chữ “Can’t solve”

Scoring

Gọi \(maxA\) là giá trị lớn nhất mảng \(A\), \(minA\) là giá trị nhỏ nhất mảng \(A\), ta có:

• \(maxA, minA\le 10^9;\)
• 30% số test có \(n\le 100, maxA-minA\le 5, T\le 10^3;\)
• 50% số test có \(n\le 200, maxA-minA\le 10, T\le 10^6;\)
• 80% số test có \(n\le 500, maxA-minA\le 500, T\le 10^9;\)
• 100% số test có \(n\le 1000,maxA-minA\le 5000, T\le 10^{12}.\)

Example

3 4
3 2 9
1 3 3
5 2 3 

1 -> 5 -> 9

3 1
3 2 9
1 3 3
5 2 3

Can't solve

Loki hay Thần lừa lọc là em trai khác cha khác mẹ của Thor, là một trong những vị thần ngoại tộc của xứ Asgard. Hiện nay hắn đang làm quản lí tại Cơ quan Quản lý Phương sai Thời gian (TVA), thế chỗ cho He who remains. Sau khi He who remains cưỡi hạc qui tiên, các sự kiện nexus xảy ra không thể kiếm soát; dẫn đến trong Đa vũ trụ xuất hiện n vũ trụ mới, Loki đánh số các vũ trụ này từ \(1\) đến \(n\) theo vị trí xuất hiện mà hắn nhìn thấy.

Công nghệ của các vũ trụ này cực kì phát triển, tới nỗi có một số cặp vũ trụ có thể liên hệ với nhau; mối liên hệ giữa hai vũ trụ là hai chiều, có nghĩa là nếu vũ trụ \(i\) có thể kết nối tới vũ trụ \(j\) thì người ở vũ trụ \(j\) cũng có thể gửi lời hồi âm tới vũ trụ \(i\). Mỗi vũ trụ có một chỉ số đặc trưng \(a_i\) được tính bằng số vũ trụ \(j (j < i)\) sao cho hai vũ trụ \(i\) và \(j\) có thể liên hệ với nhau. Dễ nhận thấy mỗi khả năng các vũ trụ liên kết với nhau sẽ chỉ cho ra duy nhất một dãy đặc trưng, song có thể có nhiều trường hợp các vũ trụ liên kết khác nhau có cùng dãy đặc trưng.

Lo sợ liên minh các vũ trụ quá hùng mạnh, và cũng để giữ sự bình ổn của Đa vũ trụ; Loki muốn xóa đi một số vũ trụ và giữ lại một số liên tiếp nhau các vũ trụ có dãy đặc trưng là \(f\) thỏa mãn:

• Tồn tại ít nhất một khả năng các vũ trụ liên kết nhau có dãy đặc trưng là \(f\)
• Trong tất cả các khả năng các vũ trụ liên kết với nhau nhận \(f\) làm dãy đặc trưng, mỗi vũ trụ có thể kết nối với không quá \(d\) vũ trụ khác

Yêu cầu:

• Cho số nguyên \(d\) và dãy đặc trưng \(a\) của \(n\) vũ trụ mới tạo ra; bạn hãy đếm số cách chọn các vũ trụ liên tiếp nhau có dãy đặc trưng thỏa mãn điều kiện trên, hay nói cách khác bạn hãy đếm số cặp \((L, R) (1 ≤ L ≤ R ≤ n)\) thỏa mãn \(a[L ... R]\) lập thành một dãy đặc trưng thỏa mãn. Hai cặp số gọi là khác nhau nếu có ít nhất một trong hai số tương ứng khác nhau

Input:

• Dòng đầu tiên chứa hai số nguyên dương \(n, d (0 ≤ d ≤ n ≤ 10^5)\)
• Dòng thứ hai chứa \(n\) số nguyên, số thứ \(i\) có giá trị \(a_i (1 ≤ i ≤ n, 0 ≤ a_i ≤ i − 1)\)

Output:

• Xuất ra một số nguyên duy nhất là số cặp số \((L, R)\) thỏa mãn

Scoring:

• Có 25% số test ứng với 25% số điểm của bài toán có \(n ≤ 200\)
• Có 25% số test ứng với 25% số điểm của bài toán có \(n ≤ 2000\)
• Có 25% số test ứng với 25% số điểm của bài toán có \(n ≤ 10^5, a_i ≥ d − 10 ∀i: 1 ≤ i ≤ n\)
• Có 25% số test ứng với 25% số điểm của bài toán có \(n ≤ 10^5\)

Example