Chạy trốn trên Beaveractor

Khuôn viên là một hình vuông kích thước $b\times b$ trên mặt phẳng: mọi điểm $(x,y)$ với $0\le x,y\le b$ đều thuộc khuôn viên.

Trong khuôn viên có $n$ mũi tên, mỗi mũi tên song song với một trong hai trục toạ độ. Các mũi tên đôi một không có điểm chung. Một cỗ máy di chuyển với vận tốc một đơn vị dài trên một đơn vị thời gian. Khi cỗ máy tới một điểm nằm trên một mũi tên nào đó, nó lập tức quay theo hướng của mũi tên đó rồi tiếp tục đi thẳng, cho tới khi lại gặp một mũi tên khác hoặc ra khỏi khuôn viên.

Cho $q$ truy vấn. Mỗi truy vấn gồm vị trí ban đầu $(x,y)$, hướng đi ban đầu $w$ (một trong U, D, L, R, tương ứng lên, xuống, sang trái, sang phải; trục $Oy$ hướng lên trên) và thời gian $t$ đã trôi qua. Với mỗi truy vấn, hãy xác định vị trí của cỗ máy sau đúng $t$ đơn vị thời gian.

Nếu cỗ máy đã ra khỏi khuôn viên trước thời điểm $t$, hãy in ra toạ độ của điểm cuối cùng thuộc khuôn viên mà nó đi qua.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $b$.
• $n$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $x_0,y_0,x_1,y_1$ là điểm đầu và điểm cuối của một mũi tên (mũi tên hướng từ $(x_0,y_0)$ tới $(x_1,y_1)$). Mọi mũi tên song song với trục toạ độ, nằm hoàn toàn trong khuôn viên và đôi một không có điểm chung.
• Dòng tiếp theo chứa số nguyên $q$.
• $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x,y$, một ký tự $w\in \{U,D,L,R\}$ và một số nguyên $t$.

Dữ liệu ra

In ra $q$ dòng. Dòng thứ $i$ chứa hai số nguyên là toạ độ của cỗ máy tại thời điểm cuối trong truy vấn thứ $i$.

Ràng buộc

• $0\le n\le 30$, $1\le b\le 30$.
• $0\le x_0,y_0,x_1,y_1\le b$.
• $1\le q\le {10}^5$.
• $0\le x,y\le b$ và $0\le t\le {10}^{15}$.

Ví dụ