Câu chuyện mối tình tay ba của những con bò trong cuộc thi VNOI CUP 2023 thật sự rất lãng mạn. Hôm nay, chúng ta cùng kể câu chuyện thù địch của những con mèo. Trong CLB H3.2, bạn Thảo My có nuôi ~n~ con mèo, nhưng dù chủ nhân rất ôn hòa, dễ tính thì ngược lại lũ mèo rất toxic. Con mèo thứ ~i~ sẽ thù địch một con mèo ~p_i~ nào đó trong những con mèo trên. Chú ý rằng, sự thù địch không có tính hai chiều (~A~ ghét ~B~ thì chưa chắc ~B~ ghét ~A~) và đôi khi có những còn mèo còn ghét chính bản thân nó. Điều thú vị là mỗi con mèo đều bị thù địch bởi đúng một con khác. Bạn My muốn giảng hòa cho các con mèo nên đã bế chúng xếp lên một bàn tròn sao cho đi theo chiều kim đồng hồ thì mỗi con mèo sẽ thù địch với con mèo ngồi liền trước nó. Sau đó bạn tìm cách khuyên nhủ chúng. Hỏi My có thể xếp được thành bao nhiêu cái bàn như thế (nếu chỉ có ~1~ mèo ghét chính mình thì cho nó ngồi ~1~ bàn ~1~ mèo)? Trong trường hợp không thể xếp được hoặc có nhiều hơn một cách xếp thì in ra ~-1.~

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~1 \le n \le 10^5.~

Dòng thứ hai là dãy số ~p_1, p_2, ..., p_n~ cho biết số thứ tự của kẻ thù địch của những con mèo, theo thông tin trên thì rõ ràng không có số nào xuất hiện nhiều lần.

Output

Số nhóm mèo thù địch mà bạn My cần đếm.

Sample input 1

4

3 4 1 2

Sample output 1

2

Sample input 2

4

1 2 3 4

Sample output 2

4

Sample input 3

4

3 1 4 2

Sample output 3

1

Giải thích: trong VD1, ta cho mèo (1,3) chung bàn, (2,4) chung bàn; trong VD2, mỗi mèo ghét chính bản thân nó nên mỗi mèo một bàn; còn trong VD3, ta có thể xếp chúng lên bàn tròn theo thứ tự (1,3,4,2) thì rõ ràng 2 con ngồi cạnh nhau sẽ ghét nhau.

Trong truyền thuyết của CLB H3.2 viết, những con cá hồi có thể vượt qua nhiều vũ môn để trở thành InfinitySalmon. Mỗi vũ môn là một chặng đường phấn đấu trong cuộc đời của con cá hồi và được đại diện bởi một con số nguyên dương. Như vậy các vũ môn sẽ tạo thành một dãy gồm ~n~ số nguyên dương tăng ngặt và vũ môn cuối cùng có giá trị không vượt quá ~m~. Con cá hồi trong câu chuyện hôm nay khá đặc biệt, nó thích trong lần thứ ~i~ (với ~1 \le i \le n~) thì giá trị vũ môn nó vượt qua sẽ có cùng số dư với ~i^2~ khi chia cho ~k~. Bạn hãy giúp con cá hồi đếm xem có bao nhiêu cách để trở thành InfinitySalmon nhé, do kết quả có thể rất lớn nên lấy modulo ~10^9+7.~

Input

Một dòng duy nhất gồm ba số nguyên dương ~n,m,k~ trong đó ~1 \le n \le 10^5~, ~1 \le m \le 10^9~, ~1 \le k \le 10^6~.

Output

Đáp số của bài toán.

Sample input 1.

2 4 2

Sample output 1.

3

Sample input 2.

12 2021 12

Sample output 2.

608212426

Giải thích. Trong VD1, con cá hồi có thể nhảy với các cách là: ~1 \to 2~ hoặc ~1 \to 4~ hoặc ~3 \to 4~.

Vào một ngày đẹp trời, tôi - "người ra đề chuẩn bị trễ deadline" - chợt nghĩ ra bài toán dựa trên một câu hỏi phỏng vấn phổ biến:

"Có một con kiến đang bò trên khối lập phương có kích thước các cạnh đều là ~1~. Nếu con kiến bò chỉ bò trên bề mặt của khối lập phương từ một điểm đầu này đến một điểm cuối, vậy thì độ dài đường đi ngắn nhất mà con kiến phải đi là bao nhiêu?"

Sau khi xem qua đề bài, tôi nhận ra đây là một bài hình học vô cùng thú vị và chứa đứng đầy sự bất ngờ cho các thí sinh. Nên tôi quyết định sẽ ra bài này cho cuộc thi sắp tới. Nhưng đến khi bắt tay vào làm đề, tôi mới bàng hoàng nhận ra, bài này không hề đơn giản như những gì tôi nghĩ và mà nó còn ngốn hết thời gian để ra các bài còn lại. Vì thế, tôi quyết định sẽ chia nó thành ~2~ bài nhỏ như sau:

1. Hai điểm đầu (~x_1,y_1,z_1~) và điểm cuối (~x_2, y_2, z_2~) của con kiến nằm trên cùng một mặt phẳng.
   

1. Hai điểm đầu (~x_1,y_1,z_1~) và điểm cuối (~x_2, y_2, z_2~) của con kiến không nằm trên cùng một mặt phẳng.
   

Và cụ thể ở bài (A) này, các bạn sẽ giải bài toán nhỏ số ~1~.

Input:

• Dòng đầu tiên chứa ~6~ số thực ~x_1,y_1,z_1,x_2,y_2,z_2~ lần lượt là tọa độ của hai điểm đầu và cuối của con kiến mà trong đó ~0 \leq x_1,y_1,z_1,x_2,y_2,z_2 \leq 1~.
• Cả ~6~ giá trị trên luôn đảm bảo sẽ chỉ có tối đa ~1~ chữ số thập phân.

Output:

• Một dòng duy nhất số thực đúng chính xác ~1~ chữ số sau dấu thập phân là độ dài đường đi ngắn nhất của hai điểm đã đầu và cuối nếu chúng thuộc cùng một mặt phẳng.
• Còn nếu chúng không cùng một mặt phẳng hoặc các điểm không thuộc bề mặt của hình lập phương thì in ra ~-1~.

Sample input 1:

1 0 0 0 1 0

Sample output 1:

1.4

Sample input 2:

0.1 0.2 0.3 0 1 0

Sample output 2:

-1

Sample input 3:

0 1 1 1 1 1

Sample output 3:

1.0

Bạn Tài trong CLB H3.2 học rất giỏi nhưng cũng rất introvert. Trong một dịp CLB H3.2 đi du lịch đảo Cần Giờ, sau nhiều ngày được năn nỉ thì cuối cùng bạn ấy cũng chịu tham gia cùng team. Khu du lịch là một vùng đất rộng lớn và nắng gắt có dạng lưới ô vuông, mỗi điểm trong lưới được gán tọa độ ~(x,y)~. Team sẽ dừng chân tại hai địa điểm có tọa độ nguyên ~A~ và ~B~ đã đặt lịch từ trước. Team muốn chọn thêm một điểm ~C~ (cũng có tọa độ nguyên nhưng không thuộc đường thẳng ~AB~) để đi dạo vòng quanh giữa 3 điểm ~A,B,C~ này. Tài bị buộc phải đi dạo cùng team nhưng vì không muốn đi nhiều nên bạn đề xuất với team điểm ~C~ mà diện tích tam giác ~ABC~ đó càng nhỏ càng tốt. Hãy giúp Tài introvert xác định diện tích đó nhé.

Input

Một dòng duy nhất là tọa độ hai điểm phân biệt ~x_A, \, y_A, \, x_B, \, y_B~ là các số tự nhiên không vượt quá ~10^9.~

Output

Diện tích tam giác cần tìm, nếu là số thập phân thì làm tròn đến 1 chữ số sau dấu phẩy.

Sample Input 1.

0 1 1 0

Sample Output 1.

0.5

Sample Input 2.

5 6 23 22

Sample Output 2.

1

Giải thích: Trong VD1, Tài có thể chọn điểm ~C(0,0)~ thì diện tích tam giác ~ABC~ lúc bấy giờ là ~1/2~, là nhỏ nhất có thể. Trong VD2, Tài có nhiều cách chọn điểm ~C~ để ra được diện tích bằng ~1~, chẳng hạn như ~C(4,5),C(6,7),C(13,13),...~

Vào một ngày đẹp trời, tôi - "người ra đề chuẩn bị trễ deadline" - chợt nghĩ ra bài toán dựa trên một câu hỏi phỏng vấn phổ biến:

"Có một con kiến đang bò trên khối lập phương có kích thước các cạnh đều là ~1~. Nếu con kiến bò chỉ bò trên bề mặt của khối lập phương từ một điểm đầu này đến một điểm cuối, vậy thì độ dài đường đi ngắn nhất mà con kiến phải đi là bao nhiêu?"

Sau khi xem qua đề bài, tôi nhận ra đây là một bài hình học vô cùng thú vị và chứa đứng đầy sự bất ngờ cho các thí sinh. Nên tôi quyết định sẽ ra bài này cho cuộc thi sắp tới. Nhưng đến khi bắt tay vào làm đề, tôi mới bàng hoàng nhận ra, bài này không hề đơn giản như những gì tôi nghĩ và mà nó còn ngốn hết thời gian để ra các bài còn lại. Vì thế, tôi quyết định sẽ chia nó thành ~2~ bài nhỏ như sau:

1. Hai điểm đầu (~x_1,y_1,z_1~) và điểm cuối (~x_2, y_2, z_2~) của con kiến nằm trên cùng một mặt phẳng.
   

1. Hai điểm đầu (~x_1,y_1,z_1~) và điểm cuối (~x_2, y_2, z_2~) của con kiến không nằm trên cùng một mặt phẳng.
   

Và cụ thể ở bài (B) này, các bạn sẽ giải bài toán nhỏ số ~2~.

Input:

• Dòng đầu tiên chứa ~6~ số thực ~x_1,y_1,z_1,x_2,y_2,z_2~ lần lượt là tọa độ của hai điểm đầu và cuối của con kiến mà trong đó ~0 \leq x_1,y_1,z_1,x_2,y_2,z_2 \leq 1~. Hai điểm đó đảm bảo sẽ nằm trên hai mặt phẳng khác nhau của hình lập phương.
• Cả ~6~ giá trị trên luôn đảm bảo sẽ chỉ có tối đa ~1~ chữ số thập phân.

Output:

Một dòng duy nhất số thực đúng chính xác ~9~ chữ số sau dấu thập phân là độ dài đường đi ngắn nhất của hai điểm đã cho.

Sample input:

1 0 0 0 1 1

Sample output:

2.236067977

Thầy Tina là một tấm gương của CLB H3.2 với những bài giảng về Kỹ thuật lập trình, Đạo đức nghề nghiệp rất sâu sắc. Thầy nhấn mạnh rằng không có gì là hoàn hảo và phải biết vượt qua những khó khăn để có thể Hướng tới những vì sao. Nếu kể ra thêm thì cũng khá dài dòng nhưng hôm nay, chúng ta sẽ tìm hiểu thử một trong các bài giảng của thầy về xử lý chuỗi. Thầy rất thích các chuỗi ký tự non-palindrome, không đối xứng (là chuỗi mà đảo ngược của nó khác với chuỗi ban đầu). Thầy gọi những chuỗi như vậy là đẹp vì thầy thích những điều không hoàn hảo. Với một chuỗi ~s~ cho trước, thầy muốn cắt nó ra thành nhiều chuỗi con rời nhau mà số chuỗi đẹp trong đó là càng nhiều càng tốt (tất nhiên trong đó vẫn có thể có các chuỗi không đẹp).

Ví dụ: với chuỗi ~s_1=abcabc~, thầy có thể cắt thành ~ab~, ~ca~, ~bc~ là được ~3~ chuỗi đẹp; còn với chuỗi ~s_2=xyzz~ thì thầy có thể cắt thành ~xyz~ và ~z~ thì được ~1~ chuỗi đẹp là ~xyz~ (còn ~z~ là đối xứng nên không đẹp), chú ý rằng thầy cũng có thể giữ nguyên chuỗi ~s_2~ ban đầu vì nó cũng là một chuỗi đẹp, việc cắt ra không làm tăng số lượng chuỗi đẹp (điều này cho thấy để ra được số lượng chuỗi đẹp lớn nhất là ~1~, ta có thể có nhiều cách cắt); còn với chuỗi ~s_3=cccc~ thì không có cách cắt nào để tạo thành chuỗi đẹp nên kết quả sẽ là ~0.~

Trong một buổi thi vấn đáp, thầy có nhiều sinh viên (không quá ~10^4~ em) và có một chuỗi ký tự gốc là ~s~. Thầy muốn giao task cho mỗi SV lấy một chuỗi con từ vị trí ~L~ đến ~R~ nào đó trong ~s~ và cắt nó ra thành càng nhiều chuỗi đẹp càng tốt. Để đổi đề cho mới lạ, có thể đôi lúc thầy còn chọn một vị trí bất kỳ trong ~s~ và sửa nó lại thành một ký tự khác. Là lớp trưởng gương mẫu, Luna được thầy giao cho giải hết số bài tập này trước để thầy có đáp án mà check với các bạn coi làm đúng hay sai. Bạn hãy cùng giúp Luna thực hiện công việc này nhé.

Input

Dòng đầu tiên là một chuỗi ~s~ có độ dài ~n~ không vượt quá ~10^4~ gồm các ký tự tiếng Anh viết thường. Dòng tiếp theo là một số ~q~ cho biết số lượng câu hỏi mà thầy đặt ra cho CLB, trong đó ~1 \le q \le 10^5.~ Mỗi dòng tiếp theo trong ~q~ dòng sẽ có một trong hai dạng:

• Dạng 1: gồm một số nguyên ~k~ với ~1 \le k \le n~ và một ký tự ~c~ nào đó, cho biết sẽ gán ~s[k]=c~.

• Dạng 2: gồm hai số nguyên ~L, R~ với ~1 \le L \le R \le n~, yêu cầu tính số lượng chuỗi đẹp nhiều nhất có thể cắt ra được từ chuỗi con xét từ vị trí ~L~ đến vị trí ~R.~ Cho biết rằng có không quá ~10^4~ câu hỏi loại này.

Output

Hãy trả lời tất cả các câu hỏi dạng ~2~ ở các dòng khác nhau.

Sample input

abcabc
3
2 1 6
1 2 a
2 1 6

Sample output

3
2

Giải thích: ban đầu thì có thể cắt thành ~3~ chuỗi đẹp như trong ví dụ của đề bài, sau khi sửa ký tự ~2~ thành ~a~ thì có chuỗi mới là ~aacabc~, dễ dàng kiểm tra được chỉ có thể cắt nó được thành tối đa ~2~ chuỗi đẹp, chẳng hạn: ~aa~, ~ca~, ~bc~ (gồm ~2~ chuỗi đẹp và ~1~ chuỗi không đẹp) hoặc ~aaca~, ~bc~.

Trong bài giảng về kỹ thuật đệ quy, anh Lazyman đã kể một câu chuyện rất hay về nhà Toán học nổi tiếng: François Édouard Anatole Lucas (1842-1891). Có một dãy số được đặt theo tên ông nhằm vinh danh các nghiên cứu của ông về các dãy số nguyên có những ứng dụng quan trọng trong thực tế: dãy số Lucas.

Cách tính số Lucas khá giống số Fibonacci: bắt đầu bằng ~2~ và ~1~, mỗi số tiếp theo bằng tổng của hai số liền trước. Thậm chí công thức tổng quát của nó còn đẹp hơn so với của Fiboacci:

~{{L}_{n}}={{\left( \frac{1-\sqrt{5}}{2} \right)}^{n}}+{{\left( \frac{1+\sqrt{5}}{2} \right)}^{n}}~

Các số đầu tiên của dãy Lucas: ~2,1,3,4,7,11,18,29,47,76,123,...~

Anh Lazyman đã yêu cầu các SV của CLB H3.2 hãy cài đặt đệ quy để tính số hạng thứ ~n~ của dãy này. Các bạn đều rất hào hứng và code ra rất nhanh. Thế là anh bèn nâng độ khó lên "chút xíu" bằng cách cho số ~n~ lên lớn hơn. Điều này có thể kéo theo giá trị của dãy Lucas thu được rất lớn nên kết quả sẽ phải chia dư cho ~10^9+7.~ Bạn hãy giúp các SV của CLB H3.2 khử đệ quy cho bài này nhé!

Input:

Một số nguyên dương ~n~ duy nhất có giá trị không quá ~10^{1000}~.

Output:

Câu trả lời của bài toán.

Sample input 1.

1

Sample output 1.

2

Sample input 2.

2

Sample output 2.

1

Sample input 3.

2554496573107241984

Sample output 3.

97012495

Ghi chú: hãy đọc kỹ giới hạn của đề bài, là ~10~ mũ ~1000~, bạn không nhìn nhầm đâu.

Đôi bạn thân Banana và Vulner vừa học về các kiến thức thuật toán thú vị. Banana thì học về đồ thị hai phía, còn Vulner thì học về thành phần liên thông. Trong buổi học nhóm, hai bạn muốn vẽ một đồ thị G hai phía để cho Vulner áp dụng được các kiến thức của mình vào. Banana cho một danh sách tên người, mỗi tên độ dài từ ~2~ đến ~100~, và mỗi người sẽ thích hai con số là độ dài tên của họ ~+1~ với ~-1.~

Ví dụ: Banana sẽ thích số ~5~ và số ~7.~

Khảo sát tên thành viên của CLB H3.2, Banana vẽ ra được một đồ thị hai phía, một bên có các đỉnh ứng với tên người, một bên có các đỉnh ứng với các con số và ai thích số nào thì sẽ có cạnh nối từ tên người đó qua số tương ứng. Bây giờ Vulner muốn tìm thành phần liên thông có số đỉnh lớn nhất của ~G~ (nhắc lại: hai đỉnh thuộc cùng một thành phần liên thông nếu có đường đi từ đỉnh này đến đỉnh kia). Rất đơn giản, bạn áp dụng thuật toán tìm kiếm theo chiều sâu DFS như Sách giáo khoa. Tuy nhiên, danh sách thành viên trong CLB H3.2 không ngắn gọn như Vulner tưởng, mỗi tên người có thể xuất hiện nhiều lần và được cho bởi một danh sách gồm tên + số lần xuất hiện tương ứng. Bạn hãy giúp Vulner trả lời câu hỏi này nhé, bạn ấy rất dễ bị tổn thương nếu bí bài đấy.

Input

Dòng đầu tiên là số ~n~ cho biết danh sách các tên và số lần xuất hiện, trong đó ~1 \le n \le 2023.~ Mỗi dòng tiếp theo trong ~n~ dòng có dạng

~s~ ~m~

trong đó ~s~ là tên, gồm chữ cái đầu viết hoa, các chữ cái sau viết thường, độ dài không quá ~100~, còn ~m~ là số lần mà tên đó xuất hiện, với ~1 \le m \le 10^6.~

Output

Kích thước của thành phần liên thông lớn nhất.

Sample input 1

4
Phu 3
Trung 2
Tai 4
Loc 1

Sample output 1

13

Sample input 2

2
Coconmeongoibencuaso 1
Toithayhoavangtrencoxanh 1

Sample output 2

3

Giải thích: trong VD1, ta thấy đồ thị có ~3+2+4+1=10~ đỉnh bên phía trái ứng với các tên xuất hiện nhiền lần và ~3~ đỉnh bên phải gồm ~2,4,6~ là các con số mà họ thích (Phú, Tài, Lộc cùng thích số ~2,4~, còn Trung thích số ~4,6~). Rõ ràng các bạn trong danh sách đều cùng thích số ~4~ nên tất cả các đỉnh đều cùng một thành phần liên thông kích thước ~10+3=13~; trong VD2, ta thấy hai người này thuộc các TPLT khác nhau (người đầu thích số ~19~ và ~21~ còn người sau thích số ~23~ và ~25~), mỗi người thích hai con số nên có hai TPLT cùng kích thước ~1+2=3.~

TL channel của anh Trần Lộc là một kênh Youtube để học thuật toán rất nổi tiếng. Tuy nhiên, anh ấy đang có dự định sẽ chuyển nhượng lại trong mùa hè tới đây. Biết được tin này, đã có ~n~ khách hàng đến muốn mua đấu giá và xếp thành hàng chờ sẵn, mỗi người có một mức tài chính khác nhau (số tiền này là con số nhạy cảm mà họ không muốn cho đối thủ biết, chỉ có anh Lộc là nắm thông tin này). Tuy nhiên vì có sự xô xát xảy ra nên thư ký Trần Nhân của anh muốn sắp xếp các vị khách thành một hàng dọc theo thứ tự tăng dần của mức tài chính. Nhân vừa học được chiêu bubble sort của sếp mình nên đã thực hiện như sau: đi từ đầu dãy, gặp hai khách liên tiếp mà người đứng trước có nhiều tiền hơn người đứng sau thì đổi chỗ. Nhân thực hiện tiếp như vậy cho đến cuối hàng, sau đó lại quay về đầu và làm lại như thế cho đến khi nào không còn ai phải đổi chỗ thì thôi. Tuy nhiên, mỗi lần đổi chỗ hai người thì cũng làm lộ thông tin số tiền của họ cho đối phương biết và đồng thời, bằng cách đó cũng tốn nhiều lần đổi mới xong.

Anh Lộc sau khi biết Nhân sắp xếp như vậy đã rất tức giận và chất vấn Nhân hai vấn đề sau:

• Có bao nhiêu cặp khách đã phải đổi chỗ?
• Số lượng khách lớn nhất đôi một không được đổi chỗ với nhau (tức là chưa lộ thông tin tài chính cho nhau) là bao nhiêu?

Từ thông tin tài chính của những người đứng trong hàng lúc đầu, bạn hãy giúp Nhân trả lời câu hỏi này trước khi anh Lộc đuổi việc bạn ấy nhé.

Input:

Dòng đầu tiên gồm số nguyên dương ~n~ với ~1 \le n \le 10^5.~

Dòng tiếp theo là hoán vị của các số ~1,2,...,n~ ứng với thứ tự tài chính của các vị khách.

Output:

Câu trả lời cho hai câu hỏi của thư ký Nhân khi bị chất vấn.

Sample input 1:

4
2 1 4 3

Sample output 1:

2 2

Sample input 2:

4
1 2 4 3

Sample output 2:

1 3

Giải thích: trong VD1, ta thấy có tất cả 2 lần đổi gồm cặp ~(2,1)~ và ~(4,3)~, ngoài ra ta có thể chọn ra một người trong cặp này, một người trong cặp kia thì hai người đó chưa biết thông tin của nhau; trong VD2, ta thấy chỉ cần 1 lần đổi chỗ, ngoài ra, có thể chọn ba người ~1,2,4~ thì họ đôi một chưa đổi chỗ cho nhau lần nào.

Cho ~n~ hình chữ nhật được tạo bởi các ô vuông ~1 \times 1~. Hãy tính số lượng ô vuông ~1 \times 1~ bị ~n~ hình chữ nhật đó bao phủ.

Ví dụ: cho ~2~ hình chữ nhật lần lượt là (xem ảnh bên dưới):

• Hình chữ nhật thứ nhất có ô trái dưới nhất ~(1,5)~ và ô phải trên nhất ~(7,8)~.

• Hình chữ nhật thứ hai có ô trái dưới nhất ~(5,1)~ và ô phải trên nhất ~(8,6)~.

Vậy ta có số lượng ô ~1 \times 1~ mà ~2~ hình này đã bao phủ là ~46~ ô vuông. Vì số lượng đó có thể rất lớn nên hãy chia lấy dư cho ~10^9+7~ sau khi tính ra kết quả.

Input:

• Dòng đầu tiên là số nguyên dương ~n~ là số lượng hình chữ nhật với ~1 \le n \leq 10^5~.

• Trong ~n~ dòng kế tiếp là ~4~ số nguyên ~x_1, y_1, x_2, y_2~ lần lượt vị trí của ô dưới cùng bên trái ~(x_1,y_1)~ và ô trên cùng bên phải ~(x_2,y_2)~ của hình chữ nhật thứ ~i~, trong đó ~-10^9 \leq x_1 \leq x_2 \leq 10^9 ; -10^9 \leq y_1 \leq y_2 \leq 10^9~.

Output:

• Một dòng duy nhất chứa ~1~ số nguyên dương là số lượng ô ~1~x~1~ bị ~n~ hình bao phủ sau khi đã chia lấy dư cho ~10^9+7~.

Sample input:

2
1 5 7 8
5 1 8 6

Sample output:

46

Ghi chú: các hình chữ nhật được cho có thể trùng nhau hoặc chứa nhau.