Cho một tập hợp gồm \(a\) số \(1\), \(b\) số \(2\) và \(c\) số \(3\). Tìm cách chia tập hợp này thành một hay nhiều tập hợp con sao cho mỗi số thuộc duy nhất một tập hợp con và số lượng tập hợp con có tổng bằng \(3\) là lớn nhất có thể.

Input

• Một dòng duy nhất chứa ba số nguyên \(a\), \(b\) và \(c\) \((0 \leq a, b, c \leq 10^{9})\).

Output

• In ra một số nguyên duy nhất là số lượng tập hợp con có tổng bằng \(3\) lớn nhất tìm được.

Example

3 0 0

1

4 2 1

3

An là một cậu bé yêu thích Số học. Mỗi khi rảnh, cậu ấy sẽ tự nghĩ ra cho mình những trò chơi thú vị với những con số. Chủ Nhật ngày hôm ấy, cậu đã nghĩ ra trò chơi như sau:

Đầu tiên ta sẽ có một số nguyên không âm \(A\), ta được thực hiện hai thao tác:

• Gấp đôi giá trị của \(A\).
• Viết thêm số \(1\) ở đằng sau số \(A\) (Số được biểu diễn ở dạng thập phân).

An sau đó là nghĩ ra rất nhiều số \(A\) khác nhau, với mỗi số lại biến đổi một cách khác nhau và viết các con số ấy lên các tờ giấy. Tuy nhiên, vì là một cậu bé đãng trí, An nhanh chóng quên mất mình đã biến đổi con số nào thành con số nào. Bạn hãy trả lời giúp An nhé.

Input

• Dòng đầu tiên chứa số nguyên \(Q\) \((1 \leq Q \leq 100)\) là số lượng câu hỏi.
• Trong \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(A\) và \(B\) \((1 \leq A, B \leq 10^{9})\).

Output

• In ra \(Q\) dòng, in ra YES nếu từ \(A\) có thể tạo ra \(B\) bằng không, một hay nhiều thao tác nêu trên hoặc NO nếu ngược lại.

Example

2
2 162
4 42

YES
NO

Robin đang chơi một trò chơi hành động thế giới mở nổi tiếng vừa ra mắt gần đây. Trò chơi có rất nhiều con quỷ, mỗi con quỷ đều có điểm sức mạnh và điểm thưởng khi bị tiêu diệt. Tuy nhiên, cậu chỉ cần tiêu diệt \(n\) con quỷ quan trọng (boss) để có thể hoàn thành trò chơi.

Ban đầu Robin có \(S\) điểm sức mạnh, điểm sức mạnh cho biết cậu có thể tiêu diệt những con quỷ có điểm sức mạnh nhỏ hơn mình. Khi gặp một con quỷ có thể tiêu diệt và có điểm thưởng \(g\), điểm sức mạnh của cậu được tăng lên \(g\) đơn vị.

Do Robin là một người chỉ thích đánh boss và không muốn mất thời gian với những con quỷ không quan trọng, bạn hãy giúp Robin xác định xem cậu có thể tiêu diệt tối đa bao nhiêu con boss? Biết rằng, đây là một trò chơi thế giới mở và Robin có thể chọn boss để đánh tùy theo ý của cậu.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(S\) \((1 \leq n \leq 10^{5}, 1 \leq S\le 10^{9})\) lần lượt là số lượng boss trong game và số điểm sức mạnh ban đầu của Robin.
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(p_{i}\) và \(g_{i}\) \((1 \leq p_{i}, g_{i} \leq 10^{9})\) lần lượt là điểm sức mạnh và điểm thưởng của con boss thứ \(i\).

Output

• In ra một số nguyên duy nhất là số lượng con boss tối đa mà Robin có thể tiêu diệt nếu bỏ qua các con quỷ phụ.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 10\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^{3}\).
• Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

5 2
6 1
7 3
4 2
10 5
12 4    

0

5 3
10 7
5 3
14 10
1 2
2 1    

3

Vì có kết quả cao trong kỳ thi học sinh giỏi vừa qua nên Phát được mẹ thưởng cho một hộp màu tuyệt đẹp. Bộ màu ấy bao gồm \(n\) cây màu được xếp theo thứ tự từ trái qua phải, cây màu thứ \(i\) (\(1 \leq i \leq n\)) có màu được mô tả bởi một số nguyên \(a_i\).

Tuy nhiên, có một số sơ suất trong quá trình sản xuất nên hộp màu của Phát có thể chứa một số cây màu giống nhau. Vì là một người thích sự hoàn hảo nên Phát muốn bỏ bớt một số cây màu sao cho những cây màu còn lại đôi một phân biệt với nhau.

Để làm vậy, Phát sẽ chọn nhiều nhất một đoạn con gồm các cây màu liên tiếp rồi bỏ chúng đi, tức là, Phát sẽ chọn hai số nguyên \(l\) và \(r\) thoả mãn \(1 \leq l \leq r \leq n\) rồi bỏ các cây màu từ vị trí \(l\) đến vị trí \(r\) và giữ nguyên các cây màu còn lại.

Hãy giúp Phát tìm ra số lượng cây màu bị bỏ đi ít nhất sao cho các cây màu còn lại thoả mãn điều kiện.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \leq n \leq 10^6\)) là số lượng cây màu.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq n\)).

Output

• In ra một số nguyên duy nhất là số lượng cây màu bị bỏ đi.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 10^{2}\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 10^{3}\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \leq 10^{5}\).
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
1 1 2 2

2

5
1 4 1 4 5

2

Xét một bảng tính (ở định dạng Microsoft Excel hoặc Google Sheet) bao gồm \(m\) hàng và \(n\) cột. Các hàng được đánh số liên tiếp từ \(1\) và các cột được ký hiệu bằng các chữ cái liên tiếp A, B, C,... (dữ liệu đảm bảo bảng tính có không quá \(9\) hàng và \(26\) cột). Mỗi ô của bảng tính là giao điểm của một hàng và một cột nhất định, đồng thời được ký hiệu bằng chữ cái tượng trưng cho cột đi liền với chữ số tượng trưng cho hàng đó. Ví dụ: ô nằm giao giữa hàng \(2\) và cột B sẽ được ký hiệu là B2. Trên mỗi ô ta viết một số nguyên không âm như hình minh họa dưới đây:

Nhiệm vụ của bạn là lập trình tính chính xác giá trị của \(Q\) biểu thức phân biệt, mỗi biểu thức sẽ có dạng \(f(x,y)\), trong đó \(f=\text{MAX}\) (tượng trưng cho hàm lấy giá trị lớn nhất) hoặc \(f=\text{SUM}\) (tượng trưng cho hàm tính tổng), \(x\) sẽ là ký hiệu tọa độ của một ô hoặc một biểu thức hợp lệ khác (tương tự với \(y\)). Như trên hình minh họa, nếu ta tính giá trị biểu thức \(\text{MAX}(\text{A1}, \text{B2})\) thì kết quả nhận được là \(5\). Xét một biểu thức phức tạp hơn là \(\text{SUM}(\text{C4},\text{MAX}(\text{C2},\text{C3}))\), ta có thể biến đổi nó về dạng tương đương là \(\text{SUM}(2,6)\) để nhận được kết quả là \(8\).

Input

• Dòng đầu chứa hai số nguyên dương \(m\) và \(n\) (\(1\leq m\leq 9\) và \(1\leq n\leq 26\)).
• Dòng thứ \(i\) trong \(m\) dòng tiếp theo chứa \(n\) số nguyên không âm mô tả giá trị các ô tại hàng thứ \(i\) của bảng tính. Dữ liệu đảm bảo các số đều không vượt quá \(1000\).
• Dòng tiếp theo chứa số nguyên dương \(Q\) (\(1 \leq Q \leq 10\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa một xâu ký tự thể hiện biểu thức cần tính. Dữ liệu đảm bảo các xâu đều không chứa dấu cách và có độ dài không vượt quá \(1000\).

Output

• Gồm \(Q\) dòng chứa \(Q\) kết quả tìm được theo trình tự trong input.

Scoring

• Subtask \(1\) (\(80\%\) số điểm): Mỗi biểu thức trong \(Q\) biểu thức được cho đều có dạng \(\text{SUM}(a, b)\) hoặc \(\text{MAX}(c, d)\), trong đó \(a\), \(b\), \(c\), \(d\) là ký hiệu cho một ô nào đó trong bảng tính.
• Subtask \(2\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

4 3
2 1 9
1 5 3
4 3 6
3 2 2
3
SUM(A1,B2)
MAX(A1,B2)
SUM(C4,C1)

7
5
11

4 3
2 1 9
1 5 3
4 3 6
3 2 2
2
SUM(MAX(A1,B2),SUM(C3,C4))
SUM(C4,MAX(C2,C3))

13
8

Trên trục tọa độ \(\text{Ox}\), có hai chất điểm ban đầu đang đứng yên ở tọa độ \(x_1\) và \(x_2\). Hai điểm này bắt đầu di chuyển với vận tốc lần lượt là \(v_1, v_2\) (vận tốc tính theo (đơn vị độ dài / giây)). Hỏi tính từ thời điểm hai điểm bắt đầu đồng thời di chuyển, cần bao lâu để chúng gặp nhau?

Input

• Gồm một dòng duy nhất chứa các số \(x_1, x_2, v_1, v_2 \in \mathbb{R} \mid \max(|x_1|, |x_2|, |v_1|, |v_2|) \le 10^9\)

Output

• Gồm một dòng duy nhất chứa thời gian để hai chất điểm gặp nhau nếu có, hoặc \(-1\) nếu hai điểm này không bao giờ gặp được.

Scoring

Đáp án bạn đưa ra cần sai khác không quá \(10^{-4}\) so với đáp án của BTC. Giả sử một test có output của thí sinh là \(j\), output của BTC là \(c\), thì thí sinh được tính là giải đúng test đó nếu như \(|j-c| \le 10^{-4}\)

Example

-1 5 1 -2

2.0001

-1 5 1 1

-1

Thống kê là một học phần quan trọng trong chương trình học đại học tại Việt Nam, là nền tảng cho nhiều lĩnh vực nghiên cứu và ứng dụng khác nhau. Trong môn học này, sinh viên sẽ được giới thiệu về các phương pháp và công cụ thống kê cơ bản để phân tích dữ liệu và rút ra những kết luận có ý nghĩa từ chúng. Không chỉ là một môn học lý thuyết, thống kê cũng đòi hỏi sinh viên thực hành thông qua việc áp dụng các phương pháp thống kê vào các bài toán thực tế. Môn thống kê không chỉ giúp sinh viên hiểu rõ hơn về các phương pháp nghiên cứu khoa học mà còn cung cấp cho họ kỹ năng quan trọng để trở thành những nhà phân tích dữ liệu thành công trong lĩnh vực nghiên cứu và doanh nghiệp.

Để thực hành thống kê, Đại đã lấy ra một mẫu ngẫu nhiên gồm \(n\) mục dữ liệu. Trong tiết học thực hành đầu tiên, mỗi sinh viên cần lập trình tính toán được những thông số sau:

• Giá trị lớn nhất, gọi là \(\max\)
• Giá trị nhỏ nhất, gọi là \(\min\)
• Giá trị trung bình, là \(\texttt{avg}\) (kí hiệu toán chuẩn: \(\mu\))
• Giá trị trung vị \(\texttt{median}\): được định nghĩa là giá trị nằm giữa trong một dãy số đã sắp xếp. Trong trường hợp \(n\) chẵn thì lấy giá trị ở bên phải trong hai giá trị ở giữa.
• Mode của tập hợp \(\texttt{mode}\) là giá trị xuất hiện nhiều nhất trong mẫu.
• Độ lệch chuẩn \(\sigma\) (\(\texttt{sigma}\), phiên âm là xích-ma): Được tính theo công thức: \(\sigma = \sqrt{\frac{\sum_i^n{(x_i - \mu)^2}}{n}}\).

Yêu cầu: Cho trước \(n\) và \(n\) số của dãy \(a\) tương ứng với dữ liệu. Hãy tính toán các thông số trên và in ra trên từng dòng

Chú thích (dành cho học sinh): Hãy hình dung kí hiệu \(\sum_i^{n} a_i\) là for (i chạy từ 1 tới n) tổng += a[i]

Input

• Dòng đầu tiên chứa số nguyên dương \(n (1\le n\le 10^4)\)
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n (|a_i| \le 10^9)\)

Output

Gồm chính xác \(6\) dòng chứa các thông số tính được theo định dạng như sau:

max
min
avg
median
mode
sigma

Scoring

Đáp án in ra không được sai khác trong vòng 6 chữ số sau dấu thập phân.
Điểm được chia đều trên mỗi test. Với mỗi thông số bạn tính được đúng với của BTC, bạn được điểm thành phần như sau:

• \(\texttt{max}\): \(7.5\%\) số điểm của test
• \(\texttt{min}\): \(7.5\%\) số điểm của test
• \(\texttt{avg}\): \(20\%\) số điểm của test
• \(\texttt{median}\): \(20\%\) số điểm của test
• \(\texttt{mode}\): \(20\%\) số điểm của test
• \(\texttt{sigma}\): \(25\%\) số điểm của test

Lưu ý, đối với \(\texttt{mode}\), nếu có nhiều giá trị cùng xuất hiện nhiều lần nhất thì có thể in giá trị bất kì.

Example

10
7 9 2 3 6 5 1 8 100 -5

100
-5
13.600000000000
6
-5
29.059249818259

Quỳnh chơi một trò chơi như sau. Ban đầu chọn ra hai số tự nhiên \(a,b\). Tại mỗi bước, Quỳnh viết số lớn hơn trong hai số \(a,b\) lên bảng, rồi trừ nó đi một lượng bằng với số nhỏ hơn (nếu tại một thời điểm nào đó \(a = b\), Quỳnh lấy một số bất kì trừ vào số còn lại). Quỳnh dừng lại khi một trong hai số bằng \(0\). Hỏi sau khi dừng lại, tổng các số được viết trên bảng là bao nhiêu?

Hãy đưa ra đáp án sau khi chia lấy dư cho \(998244353\)

Input

• Gồm một dòng duy nhất chứa hai số nguyên dương \(a,b (1\le a,b\le 10^{18})\)

Output

• Gồm một dòng duy nhất chứa tổng cần tính, theo modulo \(998244353\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(a,b \le 10^4\)
• Subtask \(2\) (\(20\%\) số điểm): \(a,b \le 10^9\)
• Subtask \(3\) (\(20\%\) số điểm): \(a\) chia hết cho \(b\).
• Subtask \(4\) (\(30\%\) số điểm): không có ràng buộc gì thêm

Example

98 12

490