바이트랜디아 주 연합

바이트랜디아 주 연합에는 자연 경이가 아주 많다! 그중에서도 가장 신비로운 것은 의심할 여지 없이 무르베다 직사각형이다. 이곳에서는 시간과 공간이 꽤 특이하게 작동한다. 오랜 연구에도 바이트랜디아 과학자들은 이런 이상 현상이 생기는 이유를 아직 찾지 못했다. 다행히 그들은 무르베다 직사각형에서 물리 법칙이 어떻게 작동하는지는 알아냈다.

무르베다 직사각형을 하나의 큰 직사각형으로 보자. 과학자들은 이를 $2 \cdot 10^9 \times 2 \cdot 10^9$ 크기의 작은 정사각형 격자로 나누었다. 각 칸은 좌표 $(x, y)$를 가지며, $x$축은 북에서 남으로, $y$축은 서에서 동으로 향한다. 따라서 북서쪽 칸은 $(1, 1)$이고, 남동쪽 칸은 $(2 \cdot 10^9, 2 \cdot 10^9)$이다. 칸 $(x_2, y_2)$에 있는 포털이 무르베다 직사각형을 바깥 세상과 잇는 유일한 통로이다.

칸 $(x, y)$에 있다고 하자. 북, 남, 동, 서 네 방향 중 한 방향으로 움직일 수 있으며, 이때 좌표 하나가 1만큼 증가하거나 감소한다. 직사각형 밖으로 나갈 수는 없다. 예를 들어 $(2 \cdot 10^9, 42)$에서 남쪽으로 가거나 $(42, 1)$에서 서쪽으로 갈 수 없다. 그렇게 하면 독사가 가득한 깊은 협곡에 빠질 수 있다.

가장 흥미로운 점은 한 방향으로 이동하는 데 걸리는 시간이다. 칸 $(x, y)$에 있을 때 각 이동에 걸리는 시간은 다음과 같다.

• 남쪽으로 이동 ($x$ 좌표가 1 증가): $f_s(x, y) = 2xy^2 + 2y^2 + x^2$ 초가 걸린다;
• 북쪽으로 이동 ($x$ 좌표가 1 감소): $f_n(x, y) = -2xy^2 + 2y^2 + x^2$ 초가 걸린다;
• 동쪽으로 이동 ($y$ 좌표가 1 증가): $f_e(x, y) = 2x^2y + 2x^2 + y^2$ 초가 걸린다;
• 서쪽으로 이동 ($y$ 좌표가 1 감소): $f_w(x, y) = -2x^2y + 2x^2 + y^2$ 초가 걸린다.

칸과 칸 사이를 이동하는 데 걸리는 시간은 음수일 수도 있다! 이 장소는 정말로 특별하다.

과학자들은 $n$명을 무르베다 직사각형에서 구출하려 한다. 칸 $(x_1, y_1)$에 서 있는 사람마다 포털까지 가는 데 필요한 최소 시간을 구해야 한다. 이런 최솟값이 존재한다는 것은 증명되어 있으므로, 여기저기 돌아다녀서 시간을 한없이 작게 만들 수는 없다.

이 장소는 매우 특이해서, $n$명 각각에게 서로 다른 포털이 필요할 수 있다.

첫 줄에 구출할 사람의 수 $n$이 주어진다 ($1 \le n \le 5 \cdot 10^4$).

이어서 $n$개의 줄에 각각 정수 네 개 $x_1$, $y_1$, $x_2$, $y_2$가 주어진다. 이는 $i$번째 사람의 위치와 그 사람이 쓸 포털의 위치를 나타낸다 ($1 \le x_1, y_1, x_2, y_2 \le 10^9$).

$n$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 사람이 자신의 포털에 도달하는 데 걸리는 최소 시간(초)을 출력한다. 이 값은 매우 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 출력한다.