Có ba màu mắt: ~brown~, ~green~ và ~blue~. Màu mắt của đứa con được xác định từ màu mắt của hai cha mẹ theo các quy tắc sau, xét theo thứ tự:

• Nếu ít nhất một trong hai cha mẹ có màu mắt ~brown~, thì đứa con có màu mắt ~brown~.
• Ngược lại, nếu ít nhất một trong hai cha mẹ có màu mắt ~green~, thì đứa con có màu mắt ~green~.
• Nếu cả hai cha mẹ có cùng một màu mắt, thì đứa con cũng có màu mắt đó.

Cho ba giá trị màu mắt theo thứ tự: cha mẹ thứ nhất, cha mẹ thứ hai và đứa con. Một số giá trị có thể là ký tự ~.~, nghĩa là màu mắt tại vị trí đó chưa được xác định và có thể nhận bất kỳ giá trị nào trong ba màu trên.

Hãy tìm tất cả các tổ hợp hợp lệ ~(p_1, p_2, c)~ (màu mắt của cha mẹ thứ nhất, cha mẹ thứ hai và đứa con) thỏa mãn các quy tắc trên, và in ra theo thứ tự từ điển. Nếu không tồn tại tổ hợp hợp lệ nào, in ra ~Incorrect~.

Dữ liệu vào

Một dòng duy nhất chứa ba giá trị cách nhau bởi dấu cách, lần lượt là màu mắt của cha mẹ thứ nhất, cha mẹ thứ hai và đứa con. Mỗi giá trị là một trong các chuỗi ~brown~, ~green~, ~blue~, hoặc ký tự ~.~.

Dữ liệu ra

In ra tất cả các tổ hợp hợp lệ, mỗi tổ hợp trên một dòng riêng, ba giá trị trong mỗi tổ hợp cách nhau bởi dấu cách, theo thứ tự từ điển. Nếu không có tổ hợp nào hợp lệ, in ra ~Incorrect~.

Ví dụ

Ví dụ 1

Input:

blue blue blue

Output:

blue blue blue

Ví dụ 2

Input:

blue brown .

Output:

blue brown brown

Ví dụ 3

Input:

green . .

Output:

green blue green
green brown brown
green green green

Ví dụ 4

Input:

blue blue brown

Output:

Incorrect

Cho một bản đồ hình chữ nhật kích thước ~n \times m~. Mỗi ô của bản đồ thuộc về một trong ~k~ quốc gia. Tập hợp các ô của mỗi quốc gia là liên thông theo cạnh, nghĩa là từ một ô bất kỳ của một quốc gia có thể đi đến bất kỳ ô nào khác của cùng quốc gia bằng các bước di chuyển lên, xuống, trái, phải mà không đi qua lãnh thổ của quốc gia khác.

Với mỗi quốc gia ~i~, xét hình chữ nhật nhỏ nhất có các cạnh song song với các cạnh của bản đồ và chứa tất cả các ô thuộc quốc gia ~i~. Quốc gia ~i~ có yêu sách lãnh thổ đối với mọi quốc gia ~j \ne i~ có ít nhất một ô nằm trong hình chữ nhật nhỏ nhất đó.

Với mỗi quốc gia ~i~, hãy tính số lượng quốc gia mà quốc gia ~i~ có yêu sách lãnh thổ đối với chúng.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên ~n~, ~m~ và ~k~ (~1 \le n, m \le 2 \cdot 10^5~; ~1 \le k \le nm \le 2 \cdot 10^6~) — chiều cao của bản đồ, chiều rộng của bản đồ và số lượng quốc gia.

Tiếp theo là ~n~ dòng, dòng thứ ~i~ chứa ~m~ số nguyên ~a_{i,1}, a_{i,2}, \ldots, a_{i,m}~ (~1 \le a_{i,j} \le k~) — số hiệu quốc gia mà các ô ~(i, 1), (i, 2), \ldots, (i, m)~ thuộc về.

Đảm bảo rằng mỗi quốc gia trong số ~k~ quốc gia có ít nhất một ô, và tập các ô của mỗi quốc gia là liên thông theo cạnh.

Dữ liệu ra

In ra ~k~ số nguyên, số thứ ~i~ bằng số lượng quốc gia mà quốc gia ~i~ có yêu sách lãnh thổ đối với chúng.

Ví dụ

Input:

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

Output:

2 1 0 0

Cho một bảng gồm ~n~ dòng và ~m~ cột, mỗi ô chứa số ~0~ hoặc ~1~. Bạn được phép thực hiện thao tác sau bao nhiêu lần tùy ý: chọn một cột bất kỳ và hoán vị các phần tử trong cột đó theo thứ tự tùy ý (số lượng ~0~ và ~1~ trong mỗi cột không thay đổi).

Hãy tìm số dòng hoàn toàn giống nhau lớn nhất có thể thu được sau các thao tác trên.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ (~1 \le n, m \le 10^5~; ~nm \le 2 \cdot 10^5~) — số dòng và số cột.

Mỗi dòng trong ~n~ dòng tiếp theo chứa ~m~ ký tự ~0~ hoặc ~1~ — các phần tử của bảng ban đầu.

Dữ liệu ra

In ra một số nguyên — số dòng hoàn toàn giống nhau lớn nhất có thể đạt được.

Ví dụ

Input:

3 4
0101
0010
0100

Output:

2

Cho một mảng gồm ~n~ số nguyên và một số nguyên ~x~. Trong một lần thao tác, bạn có thể chọn hai phần tử liền kề của mảng có tổng bằng ~x~ và xóa cả hai phần tử đó. Sau thao tác, kích thước của mảng giảm đi ~2~ và các phần tử còn lại dồn lại liền kề nhau.

Hãy xác định xem có thể làm mảng trở thành rỗng sau một số (có thể bằng ~0~) thao tác hay không.

Dữ liệu vào

Dòng đầu chứa hai số nguyên ~n~ và ~x~ (~1 \le n \le 3 \cdot 10^5~; ~-10^9 \le x \le 10^9~) — kích thước mảng và tổng của hai phần tử bị xóa.

Dòng thứ hai chứa ~n~ số nguyên ~a_i~ (~-10^9 \le a_i \le 10^9~) — các phần tử của mảng.

Dữ liệu ra

In ra ~Yes~ nếu có thể làm mảng trở thành rỗng, ngược lại in ra ~No~.

Ví dụ

Ví dụ 1

Input:

4 10
6 7 3 4

Output:

Yes

Ví dụ 2

Input:

1 7
7

Output:

No

Ví dụ 3

Input:

6 -3
-3 -9 6 3 -6 0

Output:

Yes

Ví dụ 4

Input:

6 4
1 5 2 4 33 0

Output:

No

Có ~n~ thanh sô-cô-la. Thanh thứ ~i~ có kích thước ~w_i \times h_i~ và thuộc về Alice hoặc Bob. Trong quá trình chơi, sô-cô-la không được xoay ~90^\circ~, tức là thanh ~a \times b~ và thanh ~b \times a~ là hai thanh khác nhau.

Ta chọn một tập con không rỗng của ~n~ thanh sô-cô-la, các thanh còn lại bị loại bỏ. Với tập con đã chọn, Alice và Bob cùng chơi một trò chơi: Alice đi trước, hai người đi luân phiên.

Trong lượt của mình, Alice thực hiện đúng một trong hai hành động:

• Ăn toàn bộ các mảnh thuộc một thanh sô-cô-la của cô ấy (tức với một chỉ số ~i~ sao cho ~o_i = 0~, tất cả các mảnh của thanh có tổng kích thước ~w_i \times h_i~ — một số mảnh có thể đã được tạo ra do các thao tác chia trước đó — bị loại khỏi trò chơi).
• Chia một mảnh hiện tại của một thanh sô-cô-la bất kỳ (không nhất thiết là của mình). Nếu mảnh được chia có kích thước ~a \times b~, thì kết quả là hai mảnh có kích thước ~x \times b~ và ~(a - x) \times b~, trong đó ~x~ là một số Fibonacci thỏa mãn ~0 < x < a~.

Trong lượt của mình, Bob thực hiện đúng một trong hai hành động:

• Ăn toàn bộ các mảnh thuộc một thanh sô-cô-la của anh ấy (tức với một chỉ số ~i~ sao cho ~o_i = 1~, tất cả các mảnh của thanh có tổng kích thước ~w_i \times h_i~ bị loại khỏi trò chơi).
• Chia một mảnh hiện tại của một thanh sô-cô-la bất kỳ. Nếu mảnh được chia có kích thước ~a \times b~, thì kết quả là hai mảnh có kích thước ~a \times y~ và ~a \times (b - y)~, trong đó ~y~ là một số Fibonacci thỏa mãn ~0 < y < b~.

Trò chơi kết thúc khi đến lượt một người chơi mà người đó không có nước đi hợp lệ nào. Người không thể đi bị thua.

Hai tập con được coi là khác nhau nếu tồn tại một chỉ số ~i \in \{1, \ldots, n\}~ sao cho thanh thứ ~i~ có trong tập con này nhưng không có trong tập con kia.

Hãy tính số tập con không rỗng mà Alice thắng khi cả hai người chơi chơi tối ưu, lấy phần dư khi chia cho ~998244353~.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên ~n~ — số thanh sô-cô-la (~1 \le n \le 100~).

Mỗi dòng trong ~n~ dòng tiếp theo chứa ba số nguyên ~w_i~, ~h_i~ và ~o_i~ — chiều rộng, chiều cao của thanh thứ ~i~ và chủ sở hữu của nó (~1 \le w_i, h_i \le 50~; ~o_i \in \{0, 1\}~). Nếu ~o_i = 0~ thì thanh thứ ~i~ thuộc về Alice, nếu ~o_i = 1~ thì thuộc về Bob.

Dữ liệu ra

In ra một số nguyên: số tập con không rỗng mà Alice thắng, lấy theo modulo ~998244353~.

Ví dụ

Ví dụ 1

Input:

2
1 1 0
1 1 1

Output:

1

Ví dụ 2

Input:

4
2 2 0
1 2 1
2 1 1
1 1 0

Output:

6

Có ~n~ quả cầu được xếp thành một hàng, đánh số từ trái sang phải. Quả cầu thứ ~i~ có sức mạnh ~a_i~. Bạn cần sắp xếp các quả cầu sao cho sức mạnh của chúng không giảm theo thứ tự từ trái sang phải.

Trong một thao tác, bạn có thể chọn hai vị trí ~i~ và ~j~ rồi đổi chỗ hai quả cầu ở hai vị trí đó. Chi phí của thao tác này là ~(|i - j| - 2)^2~.

Hãy tính tổng chi phí nhỏ nhất để sắp xếp các quả cầu theo thứ tự không giảm.

Cho ~t~ truy vấn độc lập.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên ~t~ (~1 \le t \le 2 \cdot 10^5~) — số truy vấn.

Tiếp theo là mô tả của ~t~ truy vấn. Mỗi truy vấn có dạng:

• Dòng đầu chứa một số nguyên ~n~ (~1 \le n \le 2 \cdot 10^5~) — số quả cầu.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~0 \le a_i \le 10^9~) — sức mạnh của các quả cầu.

Đảm bảo tổng ~n~ trên tất cả các truy vấn không vượt quá ~2 \cdot 10^5~.

Dữ liệu ra

Với mỗi truy vấn, in ra trên một dòng một số nguyên — tổng chi phí nhỏ nhất để hoàn thành nghi lễ.

Ví dụ

Input:

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

Output:

0
1
2

Cho một mảng các khóa nguyên đôi một phân biệt ~x_1 < x_2 < \ldots < x_n~ đã được sắp xếp tăng dần và một hằng số nguyên không âm ~\varepsilon~.

Hãy chia mảng các khóa thành số đoạn con liên tiếp ít nhất sao cho trên mỗi đoạn ~[l \ldots r]~ tồn tại một hàm tuyến tính ~f(x) = k \cdot x + b~ dự đoán vị trí của khóa ~x_i~ trên đoạn đó (vị trí này bằng ~i - l~) với sai số không vượt quá ~\varepsilon~.

Một cách hình thức, với đoạn thứ ~j~ phải tồn tại các hệ số ~k_j~ và ~b_j~ (không nhất thiết nguyên) sao cho với mọi ~i \in [l_j \ldots r_j]~:

~|f_j(x_i) - (i - l_j)| \le \varepsilon~,

với ~f_j(x) = k_j \cdot x + b_j~.

Dữ liệu vào

Dòng đầu chứa hai số nguyên ~n~ và ~\varepsilon~ (~2 \le n \le 10^6~; ~0 \le \varepsilon \le n~) — số lượng khóa và sai số tối đa cho phép.

Dòng thứ hai chứa ~n~ số nguyên phân biệt ~x_1, x_2, \ldots, x_n~ theo thứ tự tăng dần (~-2 \cdot 10^9 \le x_1 < x_2 < \ldots < x_n \le 2 \cdot 10^9~).

Dữ liệu ra

In ra một số nguyên ~m~ — số đoạn con ít nhất cần chia mảng để thỏa mãn yêu cầu.

Ví dụ

Input:

8 0
1 2 3 4 7 10 13 16

Output:

2

Ghi chú

Trong ví dụ, có thể chia mảng thành hai đoạn ~[1, 2, 3, 4]~ và ~[7, 10, 13, 16]~. Trên đoạn thứ nhất, vị trí của khóa được dự đoán chính xác bởi hàm ~f(x) = x - 1~. Trên đoạn thứ hai, vị trí được dự đoán chính xác bởi hàm ~f(x) = (x - 7) / 3 = \frac{1}{3} \cdot x - \frac{7}{3}~.

Cho hai số nguyên không âm ~n~ và ~x~. Với mọi ~1 \le l \le r \le n~ cho trước số nguyên ~w_{l,r}~.

Với mảng số nguyên ~A = [a_1, a_2, \ldots, a_n]~, định nghĩa:

~f(A) = \sum_{l=1}^{n} \sum_{r=l}^{n} w_{l,r} \cdot \min(a_l, a_{l+1}, \ldots, a_r)~.

Hãy tìm giá trị lớn nhất có thể của ~f(A)~ trên tất cả các mảng ~A~ thỏa mãn ~a_1 + a_2 + \ldots + a_n = x~ và ~a_i \ge 0~ với mọi ~i~.

Dữ liệu vào

Dữ liệu vào gồm một hoặc nhiều test.

Dòng đầu chứa một số nguyên ~t~ (~1 \le t \le 50~) — số test.

Tiếp theo là mô tả của ~t~ test. Mỗi test có dạng:

• Dòng đầu chứa hai số nguyên ~n~ và ~x~ (~1 \le n \le 50~; ~1 \le x \le 10^9~).
• Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa ~n - i + 1~ số nguyên ~w_{i,i}, w_{i,i+1}, \ldots, w_{i,n}~ (~1 \le w_{i,j} \le 10^6~).

Dữ liệu ra

Với mỗi test, in ra trên một dòng một số nguyên — giá trị lớn nhất của ~f(A)~ thỏa mãn các điều kiện đã cho.

Ví dụ

Input:

3
5 10
1 1 1 1 1
1 1 1 1
1 1 1
1 1
1
1 10
1
4 1000000000
1 2 3 4
5 6 7
8 9
10

Output:

30
10
14999999995

Một thành phố có hai con đường chính: đại lộ ~H~ rộng ~\ell_H~ mét và phố ~W~ rộng ~\ell_W~ mét, cắt nhau dưới góc ~\alpha~ độ. Hai con đường này chia thành phố thành bốn khu phố.

Đèn giao thông tại giao lộ được điều khiển sao cho đèn xanh cho người đi bộ trên cả hai đường bật cùng lúc. Nhờ vậy, để di chuyển giữa hai khu phố bất kỳ (kể cả hai khu phố đối diện qua giao lộ), người đi bộ có thể đi theo đoạn thẳng ngắn nhất nối hai biên giới của hai khu phố đó.

Có ~\frac{4 \cdot (4 - 1)}{2} = 6~ cặp khu phố. Hãy viết chương trình in ra sáu số bằng các khoảng cách đôi một giữa bốn khu phố.

Dữ liệu vào

Một dòng duy nhất chứa ba số thực ~\ell_H~, ~\ell_W~ và ~\alpha~ — chiều rộng đại lộ ~H~ tính theo mét, chiều rộng phố ~W~ tính theo mét và góc giữa hai đường tính theo độ (~0.01 \le \ell_H, \ell_W \le 1000~; ~0.1 \le \alpha \le 90~). Mỗi số được cho với độ chính xác từ ~0~ đến ~3~ chữ số sau dấu phẩy thập phân.

Dữ liệu ra

In ra theo thứ tự bất kỳ sáu số thực — các khoảng cách đôi một giữa bốn khu phố tính theo mét.

Đáp án của bạn được chấp nhận nếu sai số tương đối hoặc tuyệt đối không vượt quá ~10^{-6}~. Một cách hình thức, nếu ~\{a_i\}_{i \in [1..6]}~ là đáp án của bạn và ~\{b_i\}_{i \in [1..6]}~ là đáp án của ban giám khảo, đáp án được chấp nhận nếu có thể hoán vị các số trong mảng ~a~ sao cho sau khi hoán vị có ~\frac{|a_i - b_i|}{\max(b_i, 1)} \le 10^{-6}~ với mọi chỉ số ~i \in [1..6]~.

Ví dụ

Ví dụ 1

Input:

23.332 32.17 76.055

Output:

23.332 23.332000 32.17 32.170 35.95260 45.39539

Ví dụ 2

Input:

3 4 90

Output:

5 4 3 3 4 5

Ví dụ 3

Input:

400 300 70

Output:

400 300.0 613.251621126 436.073 400 300

Cho hai số nguyên ~a~ và ~b~. Hãy tìm một cặp số nguyên dương ~x~ và ~y~ sao cho:

~x \cdot y = a~ và ~x \oplus y = b~,

trong đó ~\oplus~ là phép XOR (cộng theo modulo ~2~ trên từng bit).

Nhắc lại phép XOR trên từng bit của hai số nguyên không âm: viết hai số trong hệ nhị phân, bit thứ ~i~ của kết quả bằng ~1~ khi và chỉ khi đúng một trong hai số có bit thứ ~i~ bằng ~1~. Ví dụ ~14 \oplus 7 = 1110_2 \oplus 0111_2 = 1001_2 = 9~. Trong C++, Java và Python phép XOR được ký hiệu là ~\hat{}~.

Dữ liệu vào

Dòng đầu chứa một số nguyên ~t~ (~1 \le t \le 200\,000~) — số bộ dữ liệu.

Trong ~t~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a~ và ~b~ (~1 \le a < 2^{62}~; ~0 \le b < 2^{31}~) — mô tả một bộ dữ liệu.

Đảm bảo rằng trong mỗi bộ dữ liệu, các số ~a~ và ~b~ được sinh ra như sau: chọn ngẫu nhiên đều hai số nguyên ~x~ và ~y~ trong đoạn ~[1, 2^{31} - 1]~, rồi tính ~a = x \cdot y~ và ~b = x \oplus y~. Do đó luôn tồn tại đáp án hợp lệ.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng hai số nguyên dương ~x~ và ~y~ cách nhau bởi dấu cách, sao cho ~x \cdot y = a~ và ~x \oplus y = b~.

Nếu có nhiều đáp án, in ra bất kỳ đáp án nào.

Ví dụ

Input:

2
21 4
9 0

Output:

7 3
3 3

Trong một năm, biết hai điều kiện sau:

• Năm đó không phải là năm nhuận.
• Số thứ Năm trong các tháng mùa đông của năm nhiều hơn số thứ Hai trong các tháng mùa đông đúng ~2~.

Các tháng mùa đông là tháng ~12~, tháng ~1~ và tháng ~2~ (cả ba tháng đều thuộc cùng năm đó). Trong năm không nhuận, tháng ~1~, ~3~, ~5~, ~7~, ~8~, ~10~, ~12~ có ~31~ ngày; tháng ~4~, ~6~, ~9~, ~11~ có ~30~ ngày; tháng ~2~ có ~28~ ngày.

Có thể chứng minh rằng hai điều kiện trên xác định duy nhất thứ trong tuần của ngày ~1~ tháng ~1~. Cho một ngày cụ thể trong năm, hãy in ra thứ trong tuần của ngày đó.

Dữ liệu vào

Một dòng duy nhất chứa một chuỗi ở dạng ~\text{DD-MM}~ — ngày và tháng (mỗi phần gồm đúng hai chữ số, ngăn cách bởi dấu gạch ngang).

Dữ liệu ra

In ra một số nguyên từ ~1~ đến ~7~ — thứ trong tuần của ngày đã cho. Quy ước: thứ Hai là ~1~, thứ Ba là ~2~, thứ Tư là ~3~, thứ Năm là ~4~, thứ Sáu là ~5~, thứ Bảy là ~6~, Chủ nhật là ~7~.

Ví dụ

Input:

16-12

Output:

3