Trong giờ học Nhập môn về lập trình, thầy Trung cho bạn Luna ba số nguyên ~a, b, c~ và một biểu thức có dạng sau đây

$$a (?) b (?) c (?)$$

trong đó ở mỗi vị trí ~(?)~, bạn Luna có thể điền vào một trong các dấu: cộng, trừ hoặc nhân. Rõ ràng mỗi vị trí có nhiều cách điền nên có thể sinh ra được nhiều kết quả khác nhau, bạn Luna muốn rằng giá trị của biểu thức tính được là càng lớn càng tốt. Chú ý rằng kết quả sẽ được tính theo thứ tự ưu tiên: nhân chia trước, cộng trừ sau và sẽ tính từ trái sang phải (không được thêm dấu ngoặc vào). Hãy giúp Luna chọn cách điền hợp lý và tìm được giá trị lớn nhất có thể.

Input

Dòng đầu tiên chứa 3 số nguyên ~a, b, c~. Biết ~|a|, |b|, |c| ≤ 10^5~

Output

Một dòng duy nhất là giá trị lớn nhất có thể đạt được.

Subtask

• Subtask 1 (50 điểm): Cả ba số ~a, b, c~ đều dương
• Subtask 2 (50 điểm): Không giới hạn gì thêm

Sample Input 1

19 6 7

Sample Ouput 1

798

Sample Input 2

3 2 -1

Sample Ouput 2

7

Giải thích

Ở test đầu tiên, bạn có thể điền vào giữa các dấu nhân để thu được kết quả 19 × 6 × 7 = 798.

Ở test sau, bạn có thể điền như sau ~3 × 2 - (-1) = 7~. Ta có thể kiểm tra được rằng không còn cách điền nào khác để thu được kết quả lớn hơn.

Trong lúc thưởng thức những miếng bánh trung thu bên tách trà đậm vị, thầy Thư và thầy Trung đã cùng thảo luận về đam mê của mình là bộ môn số học. Những con số luôn có sức hút kỳ lạ và có thể giúp những người bận rộn nhất ngồi đàm đạo hàng giờ cùng nhau. Thầy Thư bèn ra một đề bài để thử thách đồng nghiệp của mình như sau: ban đầu, thầy Trung được cho hai số 1 và thầy được thực hiện một hoặc nhiều thao tác

• Mỗi thao tác, thầy Trung được phép chọn một số nguyên dương ~k~ nào đó và nhân ~k~ vào một trong hai số, số còn lại thì nhân thêm ~k^2~. Chú ý rằng lựa chọn này là độc lập giữa các lần, tức là lần trước chọn số này, lần sau có thể chọn số khác đều được.

Thầy Thư đặt vấn đề là liệu rằng có thể tạo ra được hai số nguyên dương ~a, b~ từ các phép biến đổi trên hay không? Bạn hãy cùng thầy Trung hoàn thành thử thách này nhé; nếu trả lời đúng, biết đâu sẽ được tặng những cái bánh ngon bổ dưỡng còn sót lại của mùa trung thu này đấy.

Input

Dòng đầu tiên là số lượng trường hợp thử ~T~, với ~1 ≤ T ≤ 34.10^4~

Mỗi tường hợp kế tếp sẽ bao gồm hai số ~1 ≤ a,b ≤ 10^9~

Output

Ứng với mỗi trường hợp, ghi Yes nếu có thể tạo được cặp số a và b nhờ các thao tác. Ngược lại thì ghi ra No.

Subtask

• Subtask 1 (70 điểm): ~T ≤ 10^3, a, b ≤ 10^5~
• Subtask 2 (30 điểm): Không giới hạn gì thêm

Sample Input 1

4
2 4
75 45
16 16
8 8

Sample Ouput 1

Yes
Yes
No
Yes

Giải thích

Ở cặp số (2, 4), ta có thể chọn ~k~ = 2 và nhân ~(k, k^2)~ vào cặp (1, 1) để thu được (2, 4). Nếu ta chọn tiếp ~k~ = 4 và nhân ~(k^2, k)~ vào thì được cặp (8, 8) như ở ví dụ cuối.

Ở cặp số (75, 45), lần 1 ta chọn ~k~ = 5 và nhân ~(k^2, k)~ vào cặp (1, 1) để được (25, 5); tiếp tục chọn ~k~ = 3 và nhân ~(k, k^2)~ vào để được (75, 45).

Ta có thể chứng minh được không có cách nào để tạo ra cặp (16, 16)..

Với sự chăm chỉ, những con kiến đã xây dựng được một thị trấn được gọi là thị trấn kiến. Thị trấn này xây dựng giống như một ma trận với H đường phố ngang và V đường phố dọc tạo thành VxH điểm giao cắt. Tất nhiên, loài kiến rất ghét nước nên mỗi khi có mưa thì thị trấn kiến trở nên hỗn loạn. Chính quyền thị trấn phải đặt một số cái dù ở một số điểm giao cắt để các con kiến trú ẩn. Tuy vậy chỉ có N điểm giao cắt được trang bị dù.

Khi bắt đầu mưa, tất cả các con kiến ở các ngã tư khác nhau bắt đầu chạy dọc theo các đường phố đến ngã tư gần nó nhất mà có dù. Tuy nhiên có một vài điểm giao cắt có nhiều hơn một điểm giao cắt có dù gần nó nhất. Những con kiến ở các giao cắt này sẽ không biết được cần phải chạy tới đâu do vậy chúng sẽ đứng yên và chịu ướt. Các điểm giao cắt như vậy được gọi là các điểm ướt.

Ví dụ, nếu thị trấn kiến có 10 đường phố ngang và 10 đường phố dọc, có 4 điểm giao cắt có ô thì các điểm có dấu '?' là các điểm ướt (hình dưới):

Yêu cầu:

Viết chương trình xác định số lượng các điểm ướt ở thị trấn kiến.

Dữ liệu: File MARVO.INP

• Dòng đầu tiên ghi hai số nguyên H và V là số lượng đường phố ngang và dọc của thị trấn kiến (1 ≤ 𝐻, 𝑉 ≤ 30000). Các đường phố ngang đánh số từ 1 đến H, các đường phố dọc đánh số từ 1 đến V.

• Dòng thứ hai chứa số nguyên N (1≤N≤10) là số lượng các điểm giao cắt có dù.

• N dòng tiếp theo, mỗi dòng ghi hai số nguyên h và v với ý nghĩa là tại điểm giao cắt hàng h với cột v có một cái ô

Dữ liệu: File MARVO.OUT

Một số nguyên duy nhất là số lượng các điểm ướt ở thị trấn kiến

Sample Input

10 10
4
4 4
4 6
6 4
9 9

Sample Output

19

Để tạo niềm vui cho mọi người, chính quyền quyết định lắp đặt một thiết bị ở nơi công cộng. Thiết bị này giao tiếp với mọi người thông qua bàn phím và màn hình và có một số nguyên lưu bên trong bộ nhớ của nó. Ban đầu số nguyên này khởi đầu bằng 1.

Thiết bị hoạt động như sau:

• Một người gõ một số nguyên từ bàn phím

• Thiết bị sẽ nhân số trong bộ nhớ của nó với số nguyên vừa gõ và kết quả được lưu lại vào chính bộ nhớ này.

• Thiết bị sẽ hiển thị lời chào lên màn hình nếu như số trong bộ nhớ là số chính phương. Khi đó người gõ số sẽ được nhiều may mắn.

Yêu cầu: Viết chương trình, cho biết dãy số nguyên mà những người chơi lần lượt gõ, xác định xem người chơi nào sẽ là người may mắn.

Dữ liệu: File POTPUNI.INP

• Dòng đầu tiên chứa số nguyên N (1≤N≤500000) là số lượng người tham gia giao tiếp với thiết bị.

• Tiếp theo là N dòng, mỗi dòng ghi một số nguyên được gõ bởi một người theo thứ tự giao tiếp với thiết bị. Các số nguyên này nằm giữa 1 và ~10^6~.

*Chú ý rằng kết quả số trong bộ nhớ có thể vượt quá kiểu số nguyên 64 bit

Kết quả: File POTPUNI.OUT

Output ra kết quả mà mỗi người nhận được theo thứ tự. Ghi "DA" nếu kết quả là số chính phương và "NE" trong trường hợp ngược lại.

Sample Input

7
2
3
6
15
35
21
64

Sample Ouput

NE
NE
DA
NE
NE
DA
DA

Có N con châu chấu đứng xếp thành một hàng chờ xem một buổi biểu diễn. Việc xếp hàng chờ đợi thật là buồn chán nên chúng thực hiện một số bước nhảy cho đỡ buồn có dạng như sau:

• Con châu chấu ở vị trí A nhảy qua đầu B con châu chấu khác về phía trái

• Con châu chấu ở vị trí A nhảy qua đầu B con châu chấu khác về phía phải

Tất nhiên các con châu chấu không có cùng độ cao, do vậy khi nhảy con châu chấu phải hết sức cẩn thận để chân của nó không va phải con châu chấu khác. Chính xác hơn nó cần phải nhảy với độ cao ít nhất bằng chiều cao con châu chấu cao nhất cần phải nhảy qua. Cho dãy các bước nhảy theo trình tự, hãy xác định chiều cao tối thiểu mỗi bước nhảy.

Dữ liệu: File NOGA.INP

• Dòng đầu tiên chứa hai số nguyên N, J (2≤N≤~10^5~, 1≤J≤~10^5~) là số lượng châu chấu và số lượng bước nhảy.

• Dòng thứ hai chứa N số nguyên nhỏ hơn 105 là chiều cao của các con châu chấu ở vị trí ban đầu. Độ cao được liệt kê từ trái qua phải.

• J dòng tiếp theo, mỗi dòng mô tả một cú nhảy theo trình tự nhảy. Với mỗi dòng, đầu tiên là số nguyên A (1≤A≤N) là vị trí của con châu chấu bắt đầu nhảy, tiếp theo là ký tự 'L' hoặc 'D' tùy theo là nhảy sang trái hoặc sang phải và cuối cùng là số nguyên B (1≤B≤N) là số lượng con châu chấu cần phải nhảy qua. Các bước nhảy luôn là hợp lệ (tức là B nhỏ hơn hoặc bằng số lượng con châu chấu ở bên trái (nếu 'L') hoặc bên phải (nếu 'D') của vị trí A)

Kết quả: File NOGA.OUT

Ghi ra J dòng, mỗi dòng là chiều cao tối thiểu của một cú nhảy theo trình tự trong file input.

Sample Input

9 3
5 3 8 4 9 3 7 4 2
2 D 3
8 L 2
5 D 2

Sample Output

9
7
4

Dưới đây là phiên bản đơn giản của một trò chơi phổ biến trong các nơi công cộng ở Bingo. Một cái máy lần lượt đọc các số nguyên và những người chơi sẽ tìm các số nguyên máy vừa đọc trên các tấm thẻ của họ.

Mỗi người chơi có một tấm thẻ được chia thành N hàng, N cột trong mỗi ô được gán một số nguyên trong phạm vi từ 1 đến N2, không có số nào được ghi hai lần.

Khi máy đọc, mỗi người chơi luôn kiểm tra N số cuối cùng máy vừa đọc. Nếu như N số này, theo thứ tự, trùng với 1 hàng của tấm thẻ thì người chơi được 1 điểm.

Ví dụ, giả sử N=3 và người chơi có tấm thẻ sau:

Nếu dãy số máy đọc là 7,1,3,6,4,5,7,1,2,2,8,9,3 thì người chơi được 2 điểm bởi vì hai dãy 6,4,5 và 2,8,9 xuất hiện như là 1 hàng trên thẻ của anh ta.

Yêu cầu:

Mirko muốn biết với cùng một dãy số mà máy đã đọc, số điểm lớn nhất của một tấm thẻ là bao nhiêu?

Dữ liệu: File BINGO.INP

• Dòng đầu tiên ghi hai số nguyên N, B (2 ≤ 𝑁 ≤ 4, 1 ≤ 𝐵 ≤ 10000) là kích cỡ của thẻ và số lượng các số mà máy đọc.

• B dòng tiếp theo mỗi dòng chứa một số theo thứ tự là dãy số mà máy đọc. Tất cả các số này nằm trong phạm vi từ 1 đến N2.

Kết quả: File BINGO.OUT

Một số nguyên là số điểm lớn nhất nhận được

Sample Input

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

Sample Output

5