모든 구간 LIS

이 문제는 인터랙티브 문제이다.

길이 $N$의 숨겨진 순열 $P = [P_1, P_2, \cdots, P_N]$이 있다.

$f(l,r)$를 연속한 부분수열 $P_l,P_{l+1},\cdots,P_r$의 가장 긴 증가하는 부분수열의 길이라고 정의한다. 증가하는 부분수열에서 원소의 값은 엄격하게 증가해야 한다.

당신은 인터랙터에게 구간을 질의하여 해당 구간의 $f(l,r)$를 알 수 있다. 최대 $600$번의 질의를 사용하여 모든 $1 \leq l \leq r \leq N$에 대한 $f(l,r)$를 구하여라.

처음에 참가자의 프로그램은 정수 $N$을 입력받는다. 순열 $P$는 참가자에게 주어지지 않는다.

구간 $[l,r]$의 LIS 길이를 질의하려면 다음 형식으로 출력한다.

? $l$ $r$

질의는 $1 \leq l \leq r \leq N$을 만족해야 한다. 인터랙터는 정수 $f(l,r)$를 출력한다.

모든 값을 알아냈다면 다음 형식으로 최종 답을 출력한다.

! $a_{1,1}\ a_{1,2}\ \cdots\ a_{1,N}$ $a_{2,2}\ a_{2,3}\ \cdots\ a_{2,N}$ $\vdots$ $a_{N,N}$

각 $a_{l,r}$은 $f(l,r)$와 같아야 한다. 즉, $l$번째 줄에는 $f(l,l),f(l,l+1),\cdots,f(l,N)$을 순서대로 출력한다.

각 질의와 최종 답을 출력한 뒤에는 반드시 출력 버퍼를 flush해야 한다.

질의 횟수는 최대 $600$번이다. 올바르지 않은 질의를 출력하거나 질의 횟수를 초과하면 인터랙터는 $-1$을 출력하고 채점을 종료한다. $-1$을 입력받은 경우 프로그램을 즉시 종료해야 한다.

최종 답을 출력한 뒤에는 더 이상 출력하지 않아야 한다.

• $1 \leq N \leq 100$.
• $P$는 $1,2,\cdots,N$의 순열이다.
• 질의 횟수는 최대 $600$번이다.
• 모든 질의는 $1 \leq l \leq r \leq N$을 만족해야 한다.