Đội tuyển IUH.Why_so_easy là niềm tự hào của IUH khi giành được cúp đồng trong kỳ thi lập trình ICPC cấp khu vực châu Á. Khi đứng trên sân khấu trao giải có dạng hình chữ nhật và gốc sân khấu cũng là gốc tọa độ, ba bạn bước lên ba vị trí khác nhau (tọa độ nguyên) và họ muốn được đứng chung một vị trí. Một người trong số họ bắt đầu di chuyển đến người khác rồi hai người cùng di chuyển đến người thứ ba. Việc di chuyển sẽ theo các hướng song song với cạnh của sân khấu. Hỏi họ cần rẽ trái/phải ít nhất bao nhiêu lần để có thể đứng chung trên sân khấu để nhận cúp? Bạn hãy giúp đội tuyển có thể tính toán ra số lần này nhé.

Chia sẻ thêm: khi phỏng vấn ngẫu nhiên các thành viên trẻ của tuyển ICPC IUH trong mùa giải năm nay cảm nghĩ về việc đàn anh nhận được cúp, một em đã tự tin trả lời rằng chiếc cúp lớn nhất mà em giành được trong cả học kỳ vừa qua là cúp học!

Input

Có ba dòng và mỗi dòng gồm hai số nguyên có trị tuyệt đối không vượt quá ~10^9,~ tất cả đều phân biệt nhau.

Output

Số lần đổi hướng ít nhất (có thể không cần rẽ lần nào).

Sample input 1:

1 -1
1 1
1 2

Sample output 1:

0

Sample input 2

-1 -1
-1 3
4 3

Sample output 2:

1

Giải thích: Trong VD1, ba người đã đứng thẳng hàng nên không cần rẽ lần nào cả; trong VD2, ta thấy người ~1~ có thể đi đến người ~2~, sau đó rẽ phải để cùng đi đến người ~3~ nên tốn ~1~ lần.

Sau kỳ thi UCPC 2023 mà không nhận được món quà nào (dù đã rất cố gắng), Mạnh cũng đã trở nên hướng nội. Bạn ấy muốn đến lab H3.2 vào một ngày mà không gặp mặt ai, để gặm nhấm sự cô đơn và mau quên bớt nỗi buồn. Trong CLB H3.2, có tất cả ~n~ thành viên và họ không đi đến lab mọi lúc mọi nơi. Thành viên thứ ~i~ sẽ đến lab sau mỗi ~a_i~ ngày. Hôm nay có một thời điểm mà tất cả thành viên của CLB họp mặt để bàn kế hoạch xem Code camp mùa tới sẽ làm ở đâu và có mặt đông đủ các thành viên. Có một điều thú vị là sau không quá ~50~ năm nữa thì tất cả sẽ lại cùng có mặt ở lab ~(*).~ Hỏi trong ~m~ ngày sắp tới, trước khi Mạnh hết buồn, có bao nhiêu ngày mà bạn ấy có thể lên CLB và được ở một mình, cô đơn trọn vẹn?

Input

Dòng đầu tiên gồm số ~n,m~ với ~1 \le n \le 10^4~ và ~1 \le m \le 10^{18}.~

Dòng tiếp theo gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ không nhất thiết phân biệt và thỏa mãn ~(*),~ trong đó người thứ ~i~ sẽ đến thăm lab sau mỗi ~a_i~ ngày.

Output

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

Sample input:

2 10
2 3

Sample output:

3

Giải thích: bạn Mạnh có thể lên lab vào các ngày thứ ~1,5,7~ thì sẽ không sợ bị ai làm phiền, có tất cả ~3~ ngày. Ngoài ra, mong rằng bạn có thể chấp nhận một chút tính phi thực tế của bài toán này, vì không có ai có thể buồn hết ~10^{18}~ ngày được.

Em Phú phá phách vừa mới lớn nên đã bắt đầu tập tành xếp hình. Đây là một trò chơi giải trí lành mạnh rất kích thích phát triển tư duy. Em đã bắt đầu với các quân domino (gồm ~2~ ô vuông ghép lại), rồi tromino (gồm ~3~ ô vuông ghép lại). Hôm nay, em bắt đầu chơi với level cao hơn là tetromino gồm ~4~ ô vuông ghép lại. Chị gái mua cho em nhiều mảnh ghép có dạng tetromino (mỗi mảnh có số lượng tùy ý). Em Phú bèn lấy áo dài của chị để cắt ra thành một hình chữ nhật ~2 \times n~ để xếp lên đó cho dễ. Em đang thắc mắc là có bao nhiêu cách xếp khác nhau với các quân tetromino này để có thể phủ kín được mảnh áo dài của chị mình? Hai cách lát được xem là khác nhau nếu dùng các loại tetromino khác nhau hoặc thứ tự sắp xếp của chúng là khác nhau.

Input:

Một dòng duy nhất gồm số nguyên dương ~n~ với ~1 \le n \le 10^{18}~.

Output:

Đáp số của bài toán. Vì đáp số có thể rất lớn nên lấy modulo ~10^9+7~.

Sample input 1:

1

Sample output 1:

0

Sample input 2:

2

Sample output 2:

1

Sample input 3:

2022

Sample output 3:

12973685

Giải thích: ta thấy với ~n=1~ thì nền nhà chỉ có ~2~ ô gạch, không thể lát được, còn với ~n=2~, ta thấy nền nhà có kích thước ~2 \times 2~ nên có một cách duy nhất là dùng hình vuông.

Dự án IUH Coder đã có những bước đầu rất tươi sáng trên con đường khởi nghiệp. Để khuyến khích cho các nhân sự đồng hành cùng đội dự án, các sếp founder của dự án đã tạo các mã coupon để dành tặng cho người thân, bạn bè sau này có sử dụng dịch vụ gì của website sẽ được giảm giá. Điều đặc biệt là tất cả các chuỗi tiếng Anh in hoa và đối xứng (đọc từ hai phía đều giống nhau) đều có thể dùng làm mã coupon của dự án (tất nhiên bí mật này chỉ có các nhân sự cấp cao của dự án cùng với các thí sinh làm bài này mới biết thôi). Thầy Tina cũng được tặng một mã như thế nhưng trong lúc cào ra (giống thẻ cào điện thoại) thì thầy vô tình cào phải vài ký tự, thành ra khi nhập vào hệ thống khuyến mãi thì bị nhầm vài chỗ và thầy còn không nhớ đúng thứ tự các chữ cái trong đó. Thầy có báo cho CEO Nhân và anh ấy muốn chỉnh lại vài ký tự trong mã của thầy Tina rồi sắp xếp lại cho thích hợp để ra được một mã coupon hợp lệ, hỏi CEO cần chỉnh ít nhất mấy ký tự? Chú ý rằng việc chỉnh ký tự ở đây có nghĩa là: chọn các ký tự nào đó rồi thay bằng các ký tự khác tùy ý.

Input:

Một dòng duy nhất gồm một chuỗi ký tự tiếng Anh in hoa, độ dài không quá ~10^5.~

Output:

Số lần chỉnh ký tự ít nhất để được mã coupon hợp lệ.

Input sample 1:

AB

Output sample 1:

1

Input sample 2:

AAB

Output sample 2:

0

Giải thích: trong VD1, ta thấy mã hiện tại chưa đối xứng, ta chỉnh ~A \to B~ thì được ~BB~ là mã hợp lệ; trong VD2, tuy mã này chưa đối xứng nhưng có thể đảo lại thành ~ABA~ là đối xứng, nên CEO không cần sửa gì mà chỉ cần sắp xếp lại là được.

Trong đợt tập huấn mùa hè chuẩn bị cho kỳ thi ICPC năm sau, có một team của IUH tên là Lu senpai ureshii tham gia kỳ thi Code-end run để trải nghiệm. Sau khi vượt qua nhiều vòng, team đã được đi trải nghiệm thực tế tại cty Chợ Tốt và gặp nhiều senpai. Trong giờ nghỉ giải lao, các senpai trong cty có tổ chức một trò chơi nho nhỏ cho tất cả team tham gia. Tất cả người chơi sẽ được nhận một số nguyên có giá trị là: ~0, 1~ hoặc số nguyên tố không vượt quá ~23~. Yêu cầu của các senpai rất đơn giản: những người chơi hãy tìm cách ghép với nhau thành nhiều nhóm nhất sao cho tích các số của các thành viên trong nhóm đang giữ là bằng nhau. Các bạn hãy giúp cho các team ấy nhé, vì họ đang có tâm lý đi chơi chứ hơi lười nghĩ thuật toán.

Input:

Dòng đầu tiên gồm số nguyên dương ~n~, cho biết tổng số thành viên của các team tham gia, trong đó ~2 \le n \le 10^5.~

Dòng tiếp theo gồm ~n~ số tự nhiên, mỗi số có thể là ~0, 1~ hoặc là số nguyên tố không vượt quá ~23.~

Output:

Số nhóm nhiều nhất có thể chia ra.

Sample input 1:

4
0 1 2 3

Sample output 1:

1

Sample input 2:

4
2 2 3 3

Sample output 2:

2

Giải thích:

Trong VD1, ta thấy không có cách chia thành các nhóm nhỏ nào nên chỉ có 1 nhóm là tất cả các số ban đầu. Trong VD2, ta có thể chia thành 2 nhóm, mỗi nhóm gồm ~(2,3).~

Người ta nói không ai giàu ba họ, không ai khó ba đời. Nhưng năm nay, CLB H3.2 có một team ICPC không những chăm chỉ mà cả ba đều rất giàu mạnh, nghe đến tên thành viên thôi là đủ biết điều đó: Phú, Tài và Lộc. Ngoài những cuộc thi, họ còn đầu tư tài chính nhiều nơi và thu về được một khoản tiền lớn. Để dễ tích lũy, Tài đã đề xuất rằng nên chia nó thành các rương tiền rồi cất vào tủ sách của H3.2. Lộc đồng ý, nhưng muốn rằng số tiền trong mỗi rương phải là số đẹp, tức là lũy thừa bậc ~k>1~ của một số nguyên dương nào đó (số mũ này không nhất thiết giống nhau ở tất cả các rương tiền); ngoài ra, Lộc cũng đã mã hóa số tiền lại, chỉ giữ lại số mũ của chúng. Cuối cùng, Phú được giao nhiệm vụ lưu giữ các số mũ đó, và vì không muốn tính toán nhiều, bạn muốn tổng các số đó là nhỏ nhất có thể. Hãy giúp team tính ra giá trị đó nhé.

Input:

Số nguyên dương ~n~ với ~1 \le n \le 10^5~ cho biết số tiền của team (đơn vị tiền là đô la).

Output:

Tổng nhỏ nhất có thể có.

Sample input 1:

1

Sample output 1:

2

Sample input 2:

21

Sample output 2:

6

Sample input 3:

57

Sample output 3:

5

Giải thích: ta thấy rằng ~1 = 1^2~ nên team sẽ lưu lại số ~2~, còn ~21=1^2+2^2+4^2~ nên team sẽ lưu lại ~2+2+2=6;~ trong VD cuối, ta có ~57=49+8=7^2+2^3~ nên kết quả là ~2+3=5.~

Phiên bản này khác phiên bản (A) ở chỗ là team giàu có hơn, với tổng tài sản lên đến hàng tỷ.

Người ta nói không ai giàu ba họ, không ai khó ba đời. Nhưng năm nay, CLB H3.2 có một team ICPC không những chăm chỉ mà cả ba đều rất giàu mạnh, nghe đến tên thành viên thôi là đủ biết điều đó: Phú, Tài và Lộc. Ngoài những cuộc thi, họ còn đầu tư tài chính nhiều nơi và thu về được một khoản tiền lớn. Để dễ tích lũy, Tài đã đề xuất rằng nên chia nó thành các rương tiền rồi cất vào tủ sách của H3.2. Lộc đồng ý, nhưng muốn rằng số tiền trong mỗi rương phải là số đẹp, tức là lũy thừa bậc ~k>1~ của một số nguyên dương nào đó (số mũ này không nhất thiết giống nhau ở tất cả các rương tiền); ngoài ra, Lộc cũng đã mã hóa số tiền lại, chỉ giữ lại số mũ của chúng. Cuối cùng, Phú được giao nhiệm vụ lưu giữ các số mũ đó, và vì không muốn tính toán nhiều, bạn muốn tổng các số đó là nhỏ nhất có thể. Hãy giúp team tính ra giá trị đó nhé.

Input:

Số nguyên dương ~n~ với ~10^5 < n \le 10^{10}~ cho biết số tiền của team (đơn vị tiền là đô la).

Output:

Tổng nhỏ nhất có thể có.

Sample input 1:

100000000

Sample output 1:

2

Sample input 2:

1000000007

Sample output 2:

7

Giải thích: trong VD1, ta thấy số đã cho là ~10000^2~, còn trong VD2, ta có thể biểu diễn: ~1723^2 + 37^3 + 31575^2 = 10^9+7~ nên kết quả là ~2+2+3=7.~

Để trang trải cho dự án khởi nghiệp, các thành viên trong cty IUHCoder phải kinh doanh thêm hình thức cafe thú cưng gồm các bé mèo Anh lông dài và bé chó Pug. Để thu hút quảng cáo, các nhân viên kinh doanh, dưới sự chỉ đạo của thầy Tina, định sẽ liên tục livestream các cặp thú cưng, mỗi lần như thế sẽ có một cặp chó-mèo được lên sóng. Còn thầy Luna thì nghĩ rằng vẫn nên có một dịp đặc biệt nào đó mà hai bé chó Pug được lên sóng cùng lúc, thầy Tina đồng ý nhưng chỉ cho phép có không quá một buổi livestream như thế thôi (chú ý rằng không cho hai mèo livestream). Hiện tại dự án chưa mua được bé chó mèo nào cả, nhưng đã tính trước lịch livestream. Cụ thể là các bé thú cưng sẽ được đánh số từ ~1 \to n~ và sẽ có ~m~ buổi livestream với các cặp số thứ tự, một cặp thú cưng có thể được lên sóng nhiều lần nên các cặp số không nhất thiết phân biệt. Thầy Tina đến kiểm tra lịch phát sóng dự kiến để đi đặt mua chó mèo về. Hỏi thầy có thể làm được điều đó hay không, tức là có cách mua ~a~ con chó, ~b~ con mèo với ~a+b=n~ rồi đánh số từ ~1~ đến ~n~ để thỏa mãn điều kiện của lịch livestream đã tính sẵn hay không?

Input:

Dòng đầu tiên gồm cặp số ~n,m~ với ~n~ là số thú cưng và ~m~ là số lần livestream, trong đó ~2 \le n \le 2023~ và ~1 \le m \le 10^5.~ Trong ~m~ dòng tiếp theo sẽ có các cặp số nguyên ~(i,j)~ với ~i \ne j~, ~1 \le i, j \le n~ cho biết số thứ tự của cặp thú cưng.

Output:

In ra YES nếu thông tin là hợp lệ, ngược lại thì in ra NO.

Input sample 1:

3 3
1 2
2 3
3 1

Output sample 1:

YES

Input sample 2:

4 6
1 2
2 3
3 4
4 1
1 3
2 4

Output sample 2:

NO

Giải thích: trong VD1, thầy Tina có thể mua ~2~ chó với STT ~1,2~ và một mèo STT ~3~. Khi đó, cặp chó ~(1,2)~ sẽ được lên sóng một lần, còn lại là mèo-chó; Còn trong VD2, dễ thấy với lịch livestream như vậy, thầy Tina không có cách nào đặt mua chó-mèo được.

Ghi chú: dự án IUHCoder cũng muốn nuôi đến ~10^5~ con thú cưng lắm, nhưng đây quả là một bài toán đau đầu.

Vừa mới gia nhập hội những người sưu tập tem, Đức rất yêu thích các loại tem và đam mê sưu tập tem của các quốc gia khác nhau. Nam cũng là một người ham mê sưu tập tem và đang sở hữu một bộ sưu tập về các loại tem mà Đức rất yêu thích. Vì thế Nam mời Đức tham gia trò chơi mà người thắng sẽ giành được toàn bộ hoặc một phần bộ sưu tập của người thua.

Bắt đầu, Nam lấy ra một phong bì chứa vài con tem của nhiều quốc gia. Sau đó, Nam đề nghị Đức chọn giữa việc lấy hoặc không lấy phong bì này. Đức có thể xem nội dung phong bì trước khi đưa ra sự lựa chọn và có thể từ chối lời đề nghị việc xem và đưa ra quyết định. Thủ tục này sẽ được lặp lại ~N~ lần. Trong quá trình chơi, Đức được phép thay đổi quyết định về các lần chọn trước nếu như nghĩ rằng mình có cách làm tốt hơn. Cuối cùng, Nam sẽ khảo sát tất cả các phong bì trong sự lựa chọn cuối cùng của Đức và từ chúng Nam sẽ lấy ra một số phong bì (ít nhất phải là ~1~). Nếu như số lượng con tem của mỗi quốc gia trong số các con tem từ các phong bì mà Nam chọn ra đều chia hết cho ~P~ (có thể bằng ~0~) thì Nam là người thắng cuộc và Đức phải nộp toàn bộ bộ sưu tập của mình cho Nam. Nếu trái lại, Đức là người thắng cuộc và sẽ được nhận toàn bộ các phong bì mà Đức đã chọn. Đức nhanh chóng xác định được là trong trò chơi này chắc chắn mình luôn có cách chơi giành được tem của Nam, nên Đức đã vui vẻ nhận lời. Vấn đề đặt ra là vì phong bì chứa các con tem giá trị hơn cả bộ sưu tập tem nên Đức bây giờ là tìm cách chơi giành được nhiều nhất các phong bì quý giá này thay vì ưu tiên giành được số con tem nhiều nhất.

Hãy giúp Đức tìm cách chơi để thu được nhiều phong bì nhất từ Nam.

Input:

• Dòng đầu tiên ghi ~2~ số nguyên ~N, P~ lần lượt là số lượt chơi, số quốc gia của các con tem (~1 \leq N~, ~P \leq 300~ và ~P~ luôn đảm bảo là số nguyên tố).
• Mỗi dòng trong số ~N~ dòng tiếp theo chứa: Một số nguyên ~M~ là số lượng con tem trong phong bì thứ ~i~ và ~M~ số nguyên không âm tiếp theo ~a_i~, cho biết trong phong bì thứ ~i~ chứa các con tem của các quốc gia ~a_i~ (~0 ≤ M ≤ 10^5~, ~1 ≤ a_i ≤ 300~).

Output:

• Một dòng duy nhất chứa số lượng phong bì lớn nhất mà Đức có thể nhận.

Sample input:

4 3
3 1 2 2
3 3 2 3
3 4 4 3
6 3 2 2 1 2 3

Sample output:

3

Cho ~n~ điểm trên mặt phẳng với hệ tọa độ Đề-các vuông góc ~Oxy~. Các điểm được đánh số từ ~1~ tới ~n~, điểm thứ ~i~ có tọa độ (~x_i, y_i~). Ta nói một điểm được phủ bởi một hình vuông nếu điểm đó nằm ở miền trong của hình vuông hoặc nằm trên cạnh hình vuông.

Tìm số ~\ell~ nhỏ nhất, sao cho có thể đặt hai hình vuông có các cạnh song song với các trục tọa độ, kích thước ~\ell \times \ell~, để có thể phủ hết tất cả ~n~ điểm đã cho.

Input:

• Dòng đầu tiên chứa số nguyên dương ~n \le 10^5~;
• Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa hai số nguyên ~x_i, y_i~ trong đó ~−10^{9} \le x_i, y_i \le 10^{9}~.

Output:

• Một dòng duy nhất chứa một số nguyên là câu trả lời cho giá trị ~\ell~ của yêu cầu tương ứng.

Sample input:

7
1 1
4 2
6 3
1 4
3 5
5 5
6 6

Sample output:

3

Giải thích: test ở trên được mô tả trong ảnh đi kèm ở đề bài.