Bedao L-JIGSAW Hay Không? Hay Hay

View as PDF

Submit solution


Points: 1.80 (partial)
Time limit: 1.5s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Sau buổi tan học, ngfam rủ iostream chơi trò xếp ghép hình. Bộ ghép hình của ngfam gồm có một bảng với kích thước ~2^k \times 2^k~. Các hàng trong bảng được đánh số từ ~0~ đến ~2^k - 1~ từ trên xuống dưới, và các cột được đánh số từ ~0~ đến ~2^k - 1~ từ trái qua phải. Ô ở hàng thứ ~r~ và cột ~c~ được biểu diễn bởi cặp số ~(r, c)~. Ngoài ra bộ ghép hình có ~\frac{4^k - 1} 3~ miếng ghép hình chữ ~\texttt{L}~, được phân loại theo góc quay như dưới đây.

Tên của các miếng ghép là viết tắt của vị trí góc phần tư trống của miếng ghép: Top Left, Top Right, Bottom Right và Bottom Left.

Với bộ ghép hình này, bảng có thể được điền vào, và có duy nhất một ô trống không được điền. Ví dụ ta có thể điền vào bảng ~2^3 \times 2^3~ để ô ~(2, 4)~ trống như sau.

ngfam đố iostream điền vào bảng, sao cho ô ~(r, c)~ được bỏ trống. Nhưng không chỉ một lần, mà iostream lúc nào cũng có cách điền thỏa mãn yêu cầu của ngfram. Vì cảm thấy rằng trò chơi quá đơn giản, nên lần này iostream đố ngược lại ngfam. Và câu đố của iostream cũng ngược luôn: cho số ~k~ và số lượng miếng ghép từng loại, hãy xem ô nào sẽ là ô trống không được điền mà không được phép xoay các miêng ghép.

Đến bây giờ ngfam vẫn đang rất bí. Hãy giúp ngfam tìm đáp án cho câu đó của iostream, hoặc chỉ ra rằng không có cách điền nào thỏa mãn yêu cầu của iostream.

Input

Mỗi test bao gồm nhiều test case. Dòng đầu tiên của mỗi test chứa số lượng số test case ~t~ (~1 \le t \le 10^5~). Mỗi test case được mô tả như sau.

Mỗi test case gồm nhất một dòng chứa số nguyên ~k~ (~1 \le k \le 30~) là tham số thể hiện kích thước bảng, tiếp đó là bốn số nguyên ~cnt_\texttt{TL}~, ~cnt_\texttt{TR}~, ~cnt_\texttt{BR}~, và ~cnt_\texttt{BL}~ (~0 \le cnt_\texttt{TL}, cnt_\texttt{TR}, cnt_\texttt{BR}, cnt_\texttt{BL} \le \frac{4^k - 1} 3~) — số lượng các miếng ghép loại ~\texttt{TL}~, ~\texttt{TR}~, ~\texttt{BR}~ và ~\texttt{BL}~ lần lượt theo thứ tự.

Output

Với mỗi test case, in ra một dòng duy nhất chứa hai số nguyên ~r, c~ — vị trí hàng và cột của ô bị trống trên bảng trong trường hợp có đáp án. Trong trường hợp không có đáp án, in ra một dòng duy nhất chứa số ~-1~.

Trong trường hợp có nhiều đáp án thỏa mãn đề bài, hãy in ra đáp án bất kì.

Subtask

  • Subtask 1 (20% số điểm): ~1 \le k \le 9~.
  • Subtask 2 (80% số điểm): Không có ràng buộc gì thêm.

Sample Input

5
3 4 3 6 8
2 1 2 1 1
3 6 6 3 6
4 17 48 13 7
6 344 317 339 365

Sample Output

7 2
1 2
-1
-1
53 5

Note

Các hình dưới đây lần lượt là cách điền cho ví dụ 1, 2 và 5.

Minh họa cho ví dụ 1

Minh họa cho ví dụ 2

Minh họa cho ví dụ 5


Comments

Please read the guidelines before commenting.


There are no comments at the moment.