페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5757
서브태스크

러시안 테이블 1s 512MB

문제

러시안 테이블은 행의 길이가 n이고, 열의 길이가 m이며 (r,c) 칸의 값은 (r - 1) \cdot m + c인 이차원 배열로 나타낼 수 있다.

n=3, m=5인 러시안 테이블은 아래와 같이 구성된다.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

우리는 이 러시안 테이블을 수직 혹은 수평으로 한 번 나눠서 나뉜 양쪽 테이블의 합이 최대한 균등하도록 하고싶다.

예를 들어 위와 같은 테이블에서는 4번째 열의 왼쪽을 수직으로 나누면 왼쪽 테이블의 합은 1+2+3+6+7+8+11+12+13=63이고, 오른쪽 테이블의 합은 4+5+9+10+14+15=57로 이보다 더 차이가 적게 나누는 방법은 없다.

이런 경우 우리는 "V 4"로 테이블을 나눴다고 한다.

각 t개의 테스트 케이스 별로 n과 m이 주어졌을 때, 어떻게 잘라야 최대한 나뉜 두 테이블의 합이 균등할지 출력하시오.


입력

첫 번째 줄에는 테스트 케이스 수인 정수 t (1 \le t \le 10^5)가 주어진다.

다음 t 줄에 걸쳐 두 개의 정수 n, m(1 \le n, m \le 10^9, 2 \le n \times m \le 10^9)이 주어진다.


출력

각 테스트 케이스 별로 한 줄씩 "D x" 형식으로 출력해야 한다.

이 때, D는 수직으로 자르는 경우 'V', 수평으로 자르는 경우 'H'가 된다.

정답이 여러 개인 경우 수직으로 자르는 경우를 출력해야 하며, 그러한 경우가 여러 개라면 그 중 값이 가장 작은 경우를 출력해야 한다.


부분문제

번호 점수 조건
#120점

t = 1, 1 \le n, m \le 100

#214점

t = 1, 1 \le n, m \le 2\,000

#315점

t = 1, 1 \le n, m \le 10^7

#416점

1 \le t \le 1\,000, 1 \le n \times m \le 10\,000

#515점

1 \le t \le 100\,000, n = 1, 1 \le m \le 10^9

#620점

1 \le t \le 100\,000, 1 \le n, m \le 10^9


예제 

5
1 3
4 7
1 10
3 3
3 5
V 3
V 5
V 8
H 3
V 4

출처

Russian Olympiad in Informatics Regional 2021 2번
로그인해야 코드를 작성할 수 있어요.