eolymp
bolt
Try our new interface for solving problems
Problems

GeoGame

GeoGame

Time limit 2 seconds
Memory limit 256 MiB

Alimzhan play interesting games a lot. One of them is GeoGame. In this game you stay at the plane, and your position can be described as point (x, y) in the plane. There are enemies with special powers: mages, warriors and tricksters. Their aim to confuse Alimzhan about his position, so that he won't know where he is. Each of them can affect Alimzhan's position in some way:

  1. x y - warrior knocks and pushes by x towards OX axis, and by y towards OY axis.

  2. a b - mage in point (0, 0) rotate you around his position on a * π / b radians counterclockwise.

  3. b x y - trickster sends you in mirror world: he creates infinite mirror (some line), so that Alimzhan turns into his mirror image.

There are n actions your enemies can possibly do: A[1], A[2], ..., A[n]. Alimzhan tired of games, so he asks your to answer q queries: what is his new position after consequent effects A[l], ..., A[r] (in this order), if his starting position is (x, y)?

Input data

In the first line you are given n (1n3 * 10^5). In the next n lines you are given n actions - each action starts with t - type of operations:

1 x y - warrior's action (|x| ≤ 100, |y| ≤ 100)

2 a b - mage's action (|a| ≤ b42)

3 b x y - trickster's action - mirror (line) is defined with 2 points (b, 0) and (x, y) (|b|, |x|, |y| ≤ 100).

In the (n + 1)-th line you are given number of queries q (1q3 * 10^5).

In the new q lines you are given queries. Each query is 4 integers in format l r x y (1lrn).

Output data

For each of q queries output the final position as two real numbers. Your answer is considered correct ifyour absolute or relative error don't exceed 10^(-4).

Examples

Input example #1
3
1 -1 2
2 1 2
3 -1 -3 2
3
1 1 5 0
1 2 5 0
1 3 5 0
Output example #1
4.000000 2.000000
-2.000000 4.000000
-5.000000 1.000000
Source 2019 Fall KBTU OPEN, Problem F