Gia cảnh nhà Tú

Tú lại một lần nữa rơi vào cảnh nợ nần. May mắn thay, trong ví của anh vẫn còn hai mảnh của một tờ tiền Polymer siêu hiếm. Chủ nợ đã đồng ý xóa nợ cho Tú nếu anh có thể chứng minh rằng hai mảnh này, khi ghép lại, sẽ tạo thành một tờ tiền hình vuông hoàn hảo. Nếu Tú không thể ghép, chủ nợ sẽ cho rằng đây là tiền giả và món nợ của Tú sẽ tăng lên gấp bội.

Mỗi mảnh tiền trong tay Tú đều có hình chữ nhật. Anh có thể xoay các mảnh tiền này (90 độ) tùy ý. Để ghép lại, hai mảnh phải được đặt kề nhau, tiếp xúc hoàn toàn dọc theo một cạnh và không được chồng chéo lên nhau.

Biết được kích thước của hai mảnh tiền, bạn hãy giúp Tú xác định xem liệu anh có thể ghép chúng lại thành một hình vuông để thoát khỏi kiếp nợ lần này hay không.

Input từ file sena.inp

Dòng đầu tiên chứa một số nguyên \(t\) (\(1 \le t \le 1000\)) — số lượng bộ dữ liệu.

Mỗi bộ dữ liệu bao gồm hai dòng:

• Dòng đầu tiên chứa hai số nguyên \(w_1\) và \(h_1\) (\(1 \le w_1, h_1 \le 100\)) — chiều rộng và chiều cao của mảnh tiền thứ nhất.
• Dòng thứ hai chứa hai số nguyên \(w_2\) và \(h_2\) (\(1 \le w_2, h_2 \le 100\)) — chiều rộng và chiều cao của mảnh tiền thứ hai.

Output ra file sena.out

Với mỗi bộ dữ liệu, in ra YES nếu Tú có thể ghép hai mảnh tiền thành một hình vuông, và NO trong trường hợp ngược lại.

Ví dụ

3
3 5
2 5

4 2
4 2

4 3
4 2

YES
YES
NO

Giải thích ví dụ

• Trường hợp 1: Tú có hai mảnh tiền kích thước \(3 \times 5\) và \(2 \times 5\). Cả hai mảnh đều có một cạnh dài \(5\). Bằng cách đặt chúng cạnh nhau dọc theo cạnh có độ dài \(5\), anh ta tạo ra một tờ tiền lớn có kích thước \((3+2)\times 5\), tức là \(5 \times 5\).

• Trường hợp 2: Tú có hai mảnh tiền giống hệt nhau, kích thước \(4 \times 2\). Anh ta có thể đặt chúng cạnh nhau dọc theo cạnh có độ dài \(4\). Kết quả là một hình có kích thước \((2+2)\times 4\), tức là \(4 \times 4\).

• Trường hợp 3: Tú có hai mảnh \(4 \times 3\) và \(4 \times 2\). Dù anh có xoay các mảnh tiền như thế nào, anh cũng không thể ghép chúng để tạo ra một hình vuông. Ví dụ, ghép theo cạnh chung là \(4\), ta được hình \(4 \times (3+2) = 4 \times 5\). Không có cách nào khác để tạo ra một hình vuông.

Bước vào kì thi lần này, Mộ đã chuẩn bị rất kĩ càng cả về tư duy lẫn tâm lý. Tuy nhiên, vài ngày trước khi Mộ đi thi, những người bạn của Mộ liên tục nhắc lại những cụm từ khó nghe khiến Mộ mất tập trung khi luyện đề như "PC", "Lý", "o i", "si sa",... Lo sợ rằng điều này sẽ ảnh hưởng đến tâm lý của mình, Mộ đã nhờ thầy T ban hành luật cấm sử dụng các từ Mộ không thích và sẽ kiểm điểm khi nghe thấy bất cứ ai nhắc đến từ cấm đó. Thầy T sẽ ghi âm lại mọi câu nói của học sinh và kiểm tra xem trong câu nói đó có từ cấm hay không. Câu nói sau khi ghi âm được biểu diễn dưới dạng một chuỗi \(S\) (không bao gồm dấu cách), và từ cấm được biểu diễn bởi một chuỗi \(T\) (không bao gồm dấu cách).

Tú là một học sinh cá biệt và rất hay trêu Mộ, vậy nên khi luật cấm được ban hành, Tú sợ rằng mình sẽ bị thầy T kiểm điểm nên Hoàng đã mua một thiết bị chuyển đổi lời nói. Thiết bị này sẽ ghi âm lại câu nói của cậu và loại bỏ đi tất cả từ cấm đầu tiên xuất hiện từ trái sang phải, sau đó ghép câu nói lại và tiếp tục cho đến khi không tìm được từ cấm nữa. Ví dụ, với từ \("cha"\) là từ cấm và câu nói của Hoàng được ghi âm là \("tucchaha"\), thiết bị sẽ lược bỏ đi các từ \("cha"\), khiến cho câu nói thành \("tucha"\), cuối cùng thành \("tu"\).

Bạn là thành viên trong nhóm lập trình thiết bị của Hoàng, vậy nên hãy giúp Hoàng tránh bị thầy phạt nhé!

Input từ file tucam.inp

Dòng đầu tiên chứa chuỗi \(S \ (1 \leq |S| \leq 10^5)\).

Dòng thứ hai chứa chuỗi \(T \ (1 \leq |T| \leq min(|S|, 1000))\).

Output ra file tucam.out

In ra một chuỗi là đáp án của bài toán.

Scoring

• Subtask 1 \((25\%)\): \(|S| \leq 100\).
• Subtask 2 \((25\%)\): \(|S| \leq 1000\).
• Subtask 3 \((15\%)\): \(|T| = 1\).
• Subtask 4 \((35\%)\): Không có ràng buộc gì thêm.

Examples

tucchaha
cha

tu

Streamer ViruSs đang tổ chức một buổi stream từ thiện với mục tiêu donate là một con số khổng lồ \(M\). Để cho thử thách thêm phần thú vị, số điểm donate tích lũy qua từng ngày sẽ được tính theo giai thừa. Cụ thể, vào cuối ngày thứ \(N\), tổng số điểm anh có sẽ là \(N!\).

ViruSs muốn biết mình cần stream ít nhất bao nhiêu ngày để tổng điểm tích lũy chia hết cho mục tiêu \(M\). Vì \(M\) quá lớn, đội ngũ của anh đã giúp phân tích \(M\) ra thừa số nguyên tố. Họ cho bạn biết rằng \(M = p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_K^{e_K}\), trong đó \(p_i\) là số nguyên tố thứ \(i\) (\(p_1=2, p_2=3, p_3=5, \ldots\)).

Nhiệm vụ của bạn là tìm số ngày nhỏ nhất \(N\) để ViruSs hoàn thành thử thách.

Input từ file viruss.inp

Dòng đầu tiên chứa số nguyên \(T\) (\(1 \le T \le 10^4\)) - số lượng thử thách.

Mỗi thử thách gồm hai dòng:

• Dòng đầu tiên là số nguyên \(K\) (\(1 \le K \le 100\)).
• Dòng thứ hai chứa \(K\) số nguyên \(e_i\) (\(0 \le p_i \cdot e_i \le 10^{18}\)) - số mũ của các số nguyên tố tương ứng.

Output ra file viruss.out

Với mỗi thử thách, in ra một số nguyên dương duy nhất là số ngày \(N\) nhỏ nhất cần tìm.

Scoring

• Subtask 1 \((10\%)\): \(T = 1, p_i \cdot e_i \le 10^5\);
• Subtask 2 \((25\%)\): \(T \le 1000, p_i \cdot e_i \le 1000\);
• Subtask 3 \((30\%)\): \(T \le 10^3, p_i \cdot e_i \le 10^{18}\);
• Subtask 4 \((35\%)\): Không có ràng buộc gì thêm.

Ví dụ

1
5
1 1 1 1 1

11

Giải thích

Mục tiêu donate là \(M = 2^1 \times 3^1 \times 5^1 \times 7^1 \times 11^1 = 2310\). ViruSs cần stream đến ngày thứ 11 để tổng điểm tích lũy \((11!)\) chia hết cho \(2310\).

Ở xứ sở An Liễng nọ có một anh streamer mới mở bán khô gà. Kho của anh có thể chứa tối đa \(M\) gói khô gà và ban đầu cũng có đủ \(M\) gói trong kho. Khi bán cho khách thì kho sẽ cạn dần, nên anh streamer muốn chọn ra một số nguyên dương \(d\) để khi kho còn ít hơn \(d\) gói khô gà, anh sẽ nhập thêm vào kho để đủ \(M\) gói. Có \(N\) khách hàng, khách thứ \(i\) muốn mua \(A_i\) gói khô gà. Anh sẽ lần lượt bán cho các khách từ \(1\) đến \(N\), và quá trình bán diễn ra như sau:

• Nếu còn đủ \(A_i\) gói khô gà, anh bán cho khách đủ \(A_i\) gói và số gói khô gà trong kho giảm đi \(A_i\).
• Nếu không còn đủ \(A_i\) gói, khách hàng sẽ không thể mua đủ và trở nên bất mãn.
• Sau khi bán, nếu trong kho còn ít hơn \(d\) gói khô gà thì sẽ nhập thêm sao cho đủ \(M\) gói trong kho.

Anh streamer cần tìm số nguyên dương d nhỏ nhất để không khách hàng nào bất mãn. Nhưng vì đang bận tiếp đại tá Piqué, anh đã nhờ bạn giải quyết vấn đề này với bộ PC của mình với phần thưởng là một gói khô gà (tất nhiên là miễn phí).

Input (từ file streamer.inp)

• Dòng đầu chứa hai số nguyên dương \(N\) và \(M\).
• Dòng sau chứa \(N\) số nguyên dương \(A_1, A_2, \ldots, A_N\).

Output (ra file streamer.out)

• In ra một số nguyên dương duy nhất là \(d\) nhỏ nhất tìm được.

Scoring

Trong mọi test, \(1 \le N, M \le 5 \times 10^5\), \(1 \le A_i \le M\), \(\sum_{i=1}^N A_i \le 5 \times 10^5\)

• Subtask 1 \((40\%)\): \(N, M \le 5000\)
• Subtask 2 \((30\%)\): \(N, M, \sum_{i=1}^N A_i \le 2 \times 10^5\)
• Subtask 3 \((30\%)\): Không có giới hạn gì thêm.

Examples

7 5
3 5 1 1 1 1 5

4

Giải thích: Gọi số gói khô gà trong kho là \(x\), ban đầu \(x = 5\). Với \(d = 4\):

• Sau khách thứ 1, \(x = 5 - 3 = 2\), vì \(x < d\) nên nhập thêm để \(x = 5\).
• Sau khách thứ 2, \(x = 5 - 5 = 0\), cần nhập thêm để \(x = 5\).
• Sau khách thứ 3, \(x = 5 - 1 = 4\).
• Sau khách thứ 4, \(x = 4 - 1 = 3\), cần nhập thêm để \(x = 5\).
• Sau khách thứ 5, \(x = 5 - 1 = 4\).
• Sau khách thứ 6, \(x = 4 - 1 = 3\), cần nhập thêm để \(x = 5\).
• Sau đó ta bán đúng \(5\) gói cho khách thứ 7 và kết thúc.

Có thể chỉ ra \(4\) là \(d\) nhỏ nhất thỏa mãn. Ví dụ với \(d = 3\):

• Sau khách thứ 1, \(x = 5 - 3 = 2\), vì \(x < d\) nên nhập thêm để \(x = 5\).
• Sau khách thứ 2, \(x = 5 - 5 = 0\), cần nhập thêm để \(x = 5\).
• Sau khách thứ 3, \(x = 5 - 1 = 4\).
• Sau khách thứ 4, \(x = 4 - 1 = 3\).
• Sau khách thứ 5, \(x = 3 - 1 = 2\), cần nhập thêm để \(x = 5\).
• Sau khách thứ 6, \(x = 5 - 1 = 4\).
• Khách thứ 7 cần \(5\) gói nhưng trong kho chỉ có \(4\) nên không thỏa mãn.

Cho một cây có \(N\) đỉnh và \(K\) viên đá, viên đá thứ \(i\) ở đỉnh \(A_i\) (có thể có nhiều viên đá ở một đỉnh). Hùng muốn chọn ra một đường đi đơn từ hai đỉnh bất kì sao cho toàn bộ \(K\) viên đá đều nằm trên đường đi này, nhưng vị trí của các viên đá hiện tại có thể khiến Hùng không thể chọn được đường đi thỏa mãn. Để sửa lại, Hùng có thể thực hiện thao tác sau nhiều lần: Chọn một viên đá và di chuyển nó đến đỉnh kề cạnh với đỉnh hiện tại của nó. Tìm số thao tác tối thiểu để Hùng có thể chọn được đường đi như ý muốn.

Input (từ file hungstones.inp)

• Dòng đầu tiên chứa hai số nguyên dương \(N, K\).
• \(N - 1\) dòng sau, dòng thứ \(i\) chứa hai số nguyên \(U_i\) và \(V_i\) là cạnh thứ \(i\) của cây.
• Dòng cuối cùng chứa \(K\) số nguyên dương \(A_1, A_2, \ldots, A_K\).

Output (ra file hungstones.out)

• In ra một số nguyên duy nhất là số bước tối thiểu để Hùng đạt được mục đích.

Scoring

Trong mọi test, \(1 \le N, K \le 5 \times 10^5\), \(1 \le A_i \le N\).

• Subtask 1 \((20\%)\): \(K = 3\);
• Subtask 2 \((20\%)\): Với mọi cạnh \(U_i, V_i\), ta có \(U_i = 1\) (đồ thị hình sao);
• Subtask 3 \((15\%)\): \(N, K \le 500\);
• Subtask 4 \((15\%)\): \(N \le 2000\);
• Subtask 5 \((15\%)\): \(N \le 2 \times 10^5\);
• Subtask 6 \((15\%)\): Không có giới hạn gì thêm.

Examples

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

3