Robot Breakout

Điểm: 4,00 (OI)

Giới hạn thời gian: 3.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Có $n$ robot trên mặt phẳng toạ độ vô hạn. Robot thứ $i$ đang ở vị trí $(x_{i}, y_{i})$ .

Bạn cần gửi đúng một mệnh lệnh đến tất cả robot — gồm hai số nguyên $X$ và $Y$ . Khi nhận lệnh, mỗi robot bắt đầu di chuyển về phía $(X, Y)$ và dừng lại khi:

robot tới được $(X, Y)$ , hoặc
robot không thể tiến gần $(X, Y)$ hơn được nữa.

Bình thường, một robot có thể thực hiện 4 hành động, mỗi hành động dịch chuyển nó sang một ô kề bên:

Hành động 1: từ $(x_{c}, y_{c}) \to (x_{c} - 1, y_{c})$ (sang trái).
Hành động 2: từ $(x_{c}, y_{c}) \to (x_{c}, y_{c} + 1)$ (lên trên).
Hành động 3: từ $(x_{c}, y_{c}) \to (x_{c} + 1, y_{c})$ (sang phải).
Hành động 4: từ $(x_{c}, y_{c}) \to (x_{c}, y_{c} - 1)$ (xuống dưới).

Tuy nhiên, một số robot bị hỏng và không thể thực hiện một số hành động. Với mỗi robot $i$ , bốn số $f_{i, 1}, f_{i, 2}, f_{i, 3}, f_{i, 4} \in {0, 1}$ chỉ rõ robot có thể thực hiện hành động tương ứng hay không ( $f_{i, j} = 1$ là có, $f_{i, j} = 0$ là không).

Bạn cần chọn cặp số nguyên $X, Y$ sao cho mọi robot đều có thể tới được $(X, Y)$ . Nếu tồn tại lời giải, đảm bảo rằng có ít nhất một điểm như vậy với $| X |, | Y | \leq 10^{5}$ .

Dữ liệu vào

Dòng đầu chứa số nguyên $q$ ( $1 \leq q \leq 10^{5}$ ) — số truy vấn.

Tiếp theo là $q$ truy vấn. Mỗi truy vấn bắt đầu với một dòng chứa số nguyên $n$ ( $1 \leq n \leq 10^{5}$ ) — số robot. Sau đó $n$ dòng, dòng thứ $i$ chứa 6 số nguyên $x_{i}, y_{i}, f_{i, 1}, f_{i, 2}, f_{i, 3}, f_{i, 4}$ ( $- 10^{5} \leq x_{i}, y_{i} \leq 10^{5}$ , $0 \leq f_{i, j} \leq 1$ ).

Tổng số robot trên tất cả truy vấn không vượt quá $10^{5}$ .

Dữ liệu ra

Với mỗi truy vấn, in trên một dòng riêng:

Nếu không tồn tại điểm mà mọi robot có thể tới: in một số $0$ .
Ngược lại, in ba số nguyên $1 X Y$ cách nhau bởi dấu cách — toạ độ điểm hợp lệ, với $| X |, | Y | \leq 10^{5}$ .

Ràng buộc

$1 \leq q \leq 10^{5}$
$1 \leq n \leq 10^{5}$
Tổng số robot $\leq 10^{5}$
$- 10^{5} \leq x_{i}, y_{i} \leq 10^{5}$
$f_{i, j} \in {0, 1}$

Ví dụ

Input	Output	Giải thích
4 2 -1 -2 0 0 0 0 -1 -2 0 0 0 0 3 1 5 1 1 1 1 2 5 0 1 0 1 3 5 1 0 0 0 2 1337 1337 0 1 1 1 1336 1337 1 1 0 1 1 3 5 1 1 1 1	1 -1 -2 1 2 5 0 1 -100000 -100000	Truy vấn 1: hai robot đứng yên tại $(- 1, - 2)$ , chọn ngay điểm đó. Truy vấn 2: robot 2 chỉ đi được theo trục $y$ , robot 3 chỉ đi được sang trái — buộc $X = 2$ , $Y = 5$ . Truy vấn 3: robot 1 không sang trái được, robot 2 không sang phải được, hai ràng buộc $X \geq 1337$ và $X \leq 1336$ mâu thuẫn. Truy vấn 4: chỉ một robot, đi được mọi hướng nên mọi điểm trong giới hạn đều hợp lệ.
4 2 -1 -2 0 0 0 0 0 -2 0 0 0 0 3 1 5 1 1 1 1 2 5 0 1 0 1 3 5 1 0 0 0 2 1337 1337 0 1 1 1 1336 1337 1 1 0 1 1 3 5 1 1 1 1	0 1 2 5 0 1 -100000 -100000	Truy vấn 1: hai robot bất động tại $(- 1, - 2)$ và $(0, - 2)$ — không có điểm chung. Các truy vấn còn lại giống ví dụ 1.

Bình luận

Không có bình luận tại thời điểm này.