시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB114322233.846%

문제

크기가 $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$

예제 입력 1

10
1 3 1 1
1 3 2 1
1 3 2 2
2 3 9
2 3 6
1 5 2 2
1 5 4 2
2 5 4
2 5 22
1 5 3 2

예제 출력 1

1
8
9
2 2
3 2
17
23
1 4
4 3
24