25294번 - 달팽이와 쿼리

크기가 $N$인 이차원 달팽이 배열은 다음과 같이 정의된다.

• $N$은 $1$보다 큰 홀수이다.
• 이차원 배열의 크기는 $N \times N$이다.
• $1$보다 크거나 같고, $N^2$보다 작거나 같은 자연수가 중복없이 $1$, $2$, $\dots$, $N^2$ 순서로 시계방향 소용돌이 패턴으로 한 칸에 하나씩 들어있다.
• 가장 왼쪽 윗 칸은 $1$이다.

왼쪽 그림은 크기 $N$이 $3$, 오른쪽은 $5$인 경우 이차원 달팽이 배열이다.

쿼리는 총 두 종류가 있다.

• 1 $n$ $x$ $y$: 크기가 $n$인 이차원 달팽이 배열에서 $x$행 $y$열에 들어있는 수를 출력한다.
• 2 $n$ $z$: 크기가 $n$인 이차원 달팽이 배열에서 $z$가 들어있는 행 번호와 열 번호를 공백으로 구분해 출력한다.

행과 열의 번호는 $1$부터 시작한다.

$Q$개의 쿼리가 주어진다. 쿼리를 순서대로 수행해보자.

첫째 줄에 쿼리의 개수 $Q$가 주어진다. 둘째 줄부터 $Q$개의 줄에 쿼리가 한 줄에 하나씩 주어진다.

쿼리를 수행한 결과를 한 줄에 하나씩 순서대로 출력한다.

• $1 ≤ Q ≤ 100\,000$
• $3 ≤ n ≤ 9999$
• $1 ≤ x, y ≤ n$
• $1 ≤ z ≤ n^2$