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.

Vào tuần trước, trong một phiên toà giả định ở CLB lập trình do thủ lĩnh Sơn Tân điều hành, có nhiều thành viên UMTer đã nêu ra những định kiến phổ biến về vùng lãnh thổ công nghệ. "Công tố viên" Wattadty cho rằng các nữ sinh thì học IT sẽ khó hơn nam sinh, còn luật sư "I Tờ" thì nghĩ nữ sinh sẽ học tốt hơn nam sinh, riêng khán giả tham dự (kể cả thủ lĩnh Sơn Tân) thì cùng cho rằng nên bình đẳng giới.

Các lập luận giữa đôi bên đưa ra đều thấy có lý, Sơn Tân thấy khó xử nên bèn nghĩ ra một cách để giải quyết như sau: các khán giả (cũng là những người liên quan trực tiếp đến câu chuyện định kiến giới tính này) sẽ xếp thành một hàng dọc và mỗi lần sẽ có một bạn bước lên trên sân khấu theo đúng thứ tự đó. Mỗi khi có người bước lên sân khấu, nếu trên sân khấu có tổng số nam hơn tổng số nữ thì Wattadty sẽ vỗ tay vì quan điểm của mình đúng; ngược lại, nếu tổng số nữ hơn tổng số nam thì I TỜ sẽ vỗ tay, ngược lại hai số lượng bằng nhau thì Sơn Tân sẽ vỗ tay. Bây giờ cho biết giới tính của các bạn trong hàng, hãy thống kê lại xem Wattadty, I TỜ và Sơn Tân đã vỗ tay tổng cộng mấy lần nhé.

Input

Một chuỗi độ dài không quá ~10^5~ gồm các ký tự 'B', 'G' ứng với giới tính nam/nữ của các bạn.

Output

Ghi ra ba số nguyên cho biết số lần vỗ tay của ba bạn.

Sample Input 1

BGBGG 

Sample Ouput 1

2 1 2

Sample Input 2

GGGGGB

Sample Ouput 2

0 6 0

Giải thích

Ở test đầu, ta có thể thống kê số lượng nam-nữ lần lượt có trên sân khấu sau 5 lượt như sau: (1, 0),(1, 1),(2, 1),(2, 2),(2, 3) thì dễ thấy bạn Wattadty sẽ vỗ tay ở lần 1, 3, bạn I TỜ sẽ vỗ tay ở lần 5 còn bạn Sơn Tân sẽ vỗ tay ở lần 2, 4.

Ở test sau, dễ thấy số nữ luôn áp đảo nên bạn I TỜ vỗ tay hết cả 6 lần.

Trong giờ học Lập trình phân tích dữ liệu, thầy Thư cho Tina một mảng ~a~ gồm ~n~ số nguyên, trong đó ~n~ là số lẻ. Bạn Tina được thực hiện thao tác sau đây với mảng này:

• Chọn một phần tử trong mảng (ví dụ ~a_i~) và tăng nó lên 1 (tức là thay thế nó bằng ~a_i~ + 1).

Thầy Thư yêu cầu bạn sử dụng tối đa ~k~ thao tác, làm sao cho trung vị của mảng là lớn nhất có thể. Cho biết rằng trung vị của mảng (có kích thước lẻ) là phần tử nằm ở vị trí chính giữa sau khi mảng được sắp xếp theo thứ tự không giảm. Ví dụ, trung vị của mảng [1, 5, 2, 4, 5] là 4 vì sau khi sắp xếp, các số của mảng sẽ là [1, 2, 4, 5, 5] và số ở giữa là 4. Bạn hãy giúp Tina nhé.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ với ~1 ≤ n ≤ 2 · 10^5~, ~n~ là số lẻ và ~1 ≤ k ≤ 10^9~) cho biết số lượng phần tử trong mảng và số lượng thao tác tối đa mà Tina có thể thực hiện.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, . . . , a_n (1 ≤ a_i ≤ 10^9)~, các số không nhất thiết phân biệt.

Output

In ra một số nguyên duy nhất - trung vị lớn nhất có thể sau các phép toán.

Sample Input 1

3 2
1 3 5

Sample Ouput 1

5

Sample Input 2

3 4
1 3 5

Sample Ouput 2

6

Sample Input 3

7 7
4 1 2 4 3 4 4

Sample Ouput 3

5

Giải thích

Trong test đầu, ta được quyền thao tác tối đa 2 lần nên có thể chọn số ~a_2~ = 3 và thao tác với nó hai lần, kết quả được mảng [1, 5, 5] và trung vị là 5.

Trong test giữa, ta có thể tăng số thứ 2 lên 3 đơn vị và tăng số thứ 3 lên 1 đơn vị và thu được mảng [1, 6, 6] có trung vị là 6.

Trong test cuối, kết quả tối đa là 5, không có cách nào tạo được trung vị lớn hơn cả.

Luna và Tina là đôi bạn thân trong CLB lập trình và cũng là các UMTer chăm chỉ đọc sách. Luna thích sách đến nỗi bạn đã xây dựng một tủ sách bán giá tốt cho các bạn bè đến tham quan chọn lựa. Trong ngày đầu tiên khai trương, trên kệ sách của Luna có tất cả ~n~ cuốn sách xếp theo hàng ngang và cuốn sách thứ ~i~ từ trái sang có giá tiền là ~a_i~. Khi thấy bạn Tina đến chơi, Luna đã quyết định cho bạn mua giảm giá một dãy các cuốn sách liên tiếp trên kệ với điều kiện là trong các cuốn sách được chọn phải có đúng ~k~ cuốn có giá tiền là lẻ. Vì có quá nhiều cách chọn, Tina đang rất phân vân không biết nên chọn như thế nào, bạn hãy giúp Tina đếm xem có tất cả bao nhiêu cách mua sách nhé.

Input

Dòng đầu tiên là hai số ~n~ và ~k~, với ~k ≤ n ≤ 2.10^5~.

Dòng thứ hai chứa ~n~ số nguyên số thứ ~i~ là ~a_i~ với ~0 ≤ a_i ≤ 10^9~.(ta có thể hiểu ~a_i~ = 0 thì coi như sách miễn phí).

Output

Số cách chọn ra các cuốn sách liên tiếp sao cho chứa đúng K cuốn có giá tiền là lẻ.

Subtask

• Subtask 1 (40 điểm): ~k ≤ n ≤ 10^3~
• Subtask 2 (60 điểm): Không giới hạn gì thêm

Sample Input 1

4 2
1 3 2 3

Sample Ouput 1

3

Sample Input 2

4 0
1 5 2 7

Sample Ouput 2

1

Sample Input 3

4 4
1 5 2 7

Sample Ouput 3

0

Giải thích

Trong test đầu, ta có thể chọn các cuốn sách [1, 5], [1, 5, 2], [5, 2, 7].

Trong test giữa, vì không được có số lẻ nên chỉ có thể chọn cuốn sách [2].

Còn trong test cuối, vì cần có k = 4 số lẻ nên không có cách chọn nào thoả mã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)..

Việc cân bằng giữa học tập, làm việc và giải trí, thư giãn không chỉ là bài toán khó của người trưởng thành mà cũng là của các genZ. Tuy nhiên, các sinh viên UMT luôn tiếp cận nó theo hướng rất thoải mái và hợp lý: học hết mình mà cũng chơi hết sức. Sau mỗi kỳ thi căng thẳng, các UMTer đều sẽ cùng nhau đi du lịch, trải nghiệm và chữa lành.

Lần này khu du lịch của các bạn có ~n~ địa điểm tham quan và các địa điểm đó nối nhau bởi ~n - 1~ con đường hai chiều sao cho từ địa điểm này đều có thể đi đến địa điểm khác thông qua các con đường. Các bạn muốn tham quan ở đây trong nhiều ngày, mỗi ngày sẽ xuất phát từ một địa điểm nào đó, đi qua các con đường đến các địa điểm khác mà thoả mãn các điều kiện sau đây:

• Mỗi con đường chỉ được đi qua đúng một lần (nhưng địa điểm thì có thể qua nhiều lần).
• Trong 2 ngày bất kỳ, nhóm bạn đều có cùng đến chơi tại ít nhất một địa điểm giống nhau.

Hỏi nhóm bạn UMTers có thể thực hiện chuyến đi thoả mãn yêu cầu trên không, và nếu được thì có thể đi chơi trong ít nhất và nhiều nhất bao nhiêu ngày?

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~3 ≤ n ≤ 10^5~ cho biết số địa điểm (giả sử các địa điểm được đánh số từ 1 đến ~n~).

Trong ~n - 1~ dòng tiếp theo, mỗi dòng gồm một cặp số ~(a, b)~ với ~1 ≤ a, b ≤ n~ cho biết hai địa điểm thứ ~a, b~ có đường đi nối nhau.

Output

Nếu nhóm không thể thực hiện được chuyến đi thoả mãn thì in ra -1, ngược lại nếu có cách đi thì lần lượt in ra giá trị lớn nhất và nhỏ nhất của số ngày mà nhóm có thể tham quan, du lịch thoả mãn ràng buộc.

Sample Input 1

4
1 2
1 3
1 4

Sample Ouput 1

3 2

Sample Input 2

6
1 2
1 3
1 4
4 5
4 6

Sample Ouput 2

-1

Giải thích

Ở test đầu, nhóm có thể đi chơi trong ba ngày: ngày 1 đi từ ~1 → 2~, ngày 2 đi từ ~1 → 3~ và ngày 3 đi từ ~1 → 4~, lúc đó hai ngày bất kỳ đều có thăm chung địa điểm; hoặc nhóm chỉ đi trong hai ngày cũng được, ngày 1 đi từ ~2 → 1 → 3~ và ngày 2 đi từ ~1 → 4~.

Ở test sau, ta không có cách nào thực hiện được các chuyến đi chơi thoả mãn.