이 문제는 인터랙티브 문제(프로그램과 채점 시스템이 입출력을 통해 상호작용하는 문제)입니다.
정수 수열이 다음 두 조건을 모두 만족할 때 비영 수열이라고 부릅니다:
- 임의의 두 원소가 서로 다르다.
- 임의의 비어 있지 않은 (연속할 필요는 없는) 부분 수열의 합이 $0$과 같지 않다.
예를 들어, $(5)$, $(1, -2, 3)$, $(-3, 7, 5, -6)$은 비영 수열이지만, $(0)$, $(1, -3, 1)$, $(2, 3, -2)$, $(1, 2, 3, -4)$는 아닙니다.
양의 정수 $N$과 $X$가 주어집니다.
$-N$ 이상 $N$ 이하의 정수로 이루어진 길이 $X = 2\lfloor\sqrt{N}\rfloor - 1$인 비영 수열 $(A_1, A_2, \dots, A_X)$의 원소를 처음부터 하나씩 차례대로 출력하세요. 단, 각 원소의 부호는 그 원소를 출력하기 직전에 지정됩니다.
$R$개의 테스트 케이스가 주어지며, 각 테스트 케이스마다 채점기와 상호작용하세요.
입력
- $1 \le R \le 10^4$
- $1 \le N \le 10^4$
- $X = 2\lfloor\sqrt{N}\rfloor - 1$
- 모든 테스트 케이스에서 $N$의 합은 $10^4$을 초과하지 않는다
상호작용 프로토콜
먼저 테스트 케이스의 개수 $R$이 다음 형식으로 주어집니다:
R
그 후 다음 상호작용이 $R$번 반복됩니다.
각 테스트 케이스에 대해 양의 정수 $N$과 $X$가 다음 형식으로 주어집니다:
N X
그다음 각 $i = 1, 2, \dots, X$에 대해 이 순서대로 다음 상호작용을 수행합니다.
먼저 $A_i$의 부호 $op_i$가 다음 형식으로 주어집니다:
op_i
$op_i$는 + 또는 - 중 하나이며, 다음 의미를 가집니다:
- 만약 $op_i = \text{+}$이면, $A_i$는 양의 정수여야 합니다.
- 만약 $op_i = \text{-}$이면, $A_i$는 음의 정수여야 합니다.
그 후 지정된 부호를 가지는 $-N$ 이상 $N$ 이하의 정수 $A_i$를 한 줄에 출력합니다 (양의 정수의 경우 플러스 기호를 출력할 필요는 없습니다):
A_i
주의사항
각 출력 후에 프로그램은 반드시 표준 출력을 비워야(flush) 합니다. 그렇지 않으면 Time Limit Exceeded를 받게 됩니다.
예제
예제 입력 1
2 4 3 - - + 3 1 +
예제 출력 1
-4 -1 2 3
노트
예제 상호작용은 다음과 같이 진행됩니다:
| 입력 | 출력 | 설명 |
|---|---|---|
2 |
테스트 케이스의 개수 $R$이 주어집니다. | |
4 3 |
첫 번째 테스트 케이스의 $N, X$가 주어집니다. | |
- |
$op_1 = \text{-}$이므로 $A_1$은 음의 정수여야 합니다. | |
-4 |
$A_1 = -4$를 출력합니다. | |
- |
$op_2 = \text{-}$이므로 $A_2$는 음의 정수여야 합니다. | |
-1 |
$A_2 = -1$을 출력합니다. | |
+ |
$op_3 = \text{+}$이므로 $A_3$은 양의 정수여야 합니다. | |
2 |
$A_3 = 2$를 출력합니다. $(A_1, A_2, A_3) = (-4, -1, 2)$는 비영 수열이므로 이 테스트 케이스는 정답으로 판정됩니다. | |
3 1 |
두 번째 테스트 케이스의 $N, X$가 주어집니다. | |
+ |
$op_1 = \text{+}$이므로 $A_1$은 양의 정수여야 합니다. | |
3 |
$A_1 = 3$을 출력합니다. $(A_1) = (3)$은 비영 수열이므로 이 테스트 케이스는 정답으로 판정됩니다. |