34676번 - 가희와 신칸센 2

문제

도쿄에서 니가타를 잇는 조에츠 신칸센은 긴 터널이 많습니다. 간토평야를 지난 후 험준한 산악 지대를 통과하기 때문입니다. 이 노선은 터널, 지상 구간, 역으로 구분할 수 있습니다. 터널의 시점과 종점의 정의는 다음과 같습니다.

• 터널 $T$가 $s$에서 시작하여 $e$에서 끝난다면, 즉 구간 $[s, e)$가 터널 $T$의 구간이라면, 터널 $T$의 시점과 종점은 각각 $s,ドル $e$가 됩니다.

호기심이 많은 가희는 조에츠 신칸센 노선이 변할 때마다 해당 노선에서 가장 긴 터널과 가장 짧은 터널, 그리고 터널의 개수가 궁금해졌습니다. 가희를 도와주세요. 가장 긴 터널과 가장 짧은 터널의 정의는 다음과 같습니다.

• 가장 긴 터널은 노선 내에서 길이가 제일 긴 터널입니다. 그러한 터널이 여러 개라면, 그중 시점이 가장 작은 터널입니다.
• 가장 짧은 터널은 노선 내에서 길이가 제일 짧은 터널입니다. 그러한 터널이 여러 개라면, 그중 시점이 가장 작은 터널입니다.

입력

첫 번째 줄에 노선의 길이 $L$이 주어집니다.

두 번째 줄에 길이가 $L$인 문자열이 주어집니다. $x$번째에 있는 문자는 다음을 의미합니다.

• 구간 $[x, x+1)$에 대해 문자가 0이면 지상 구간, 1이면 터널, 2이면 역입니다.

세 번째 줄에 쿼리의 개수 $Q$가 주어집니다.

네 번쨰 줄부터 $Q$개의 줄에 걸쳐 다음 두 개의 쿼리 중 하나가 한 줄에 하나씩 주어집니다.

• 1ドル$ $s$ $e$ : 구간 $[s, e)$에 속한 모든 지상 구간에 터널을 즉시 건설합니다. 또한 새로 생긴 터널이 기존 터널과 연결되는 경우, 새로 생긴 터널은 기존 터널과 합쳐집니다. $(1 \leq s \lt e \leq L)$
• 2ドル$ : 문제에 대한 답을 출력합니다.

출력

2ドル$번 쿼리가 나올 때마다 다음과 같이 출력해 주세요.

터널이 노선 내에 없는 경우 -1만 출력해 주세요. 그렇지 않은 경우 다음 형식으로 출력해 주세요. 5ドル$개의 값은 공백으로 구분해서 출력해 주세요.

{tunnel_num} {longest_tunnel_s} {longest_tunnel_e} {shortest_tunnel_s} {shortest_tunnel_e}

각 요소에 대한 설명은 다음과 같습니다.

• tunnel_num : 조에츠 신칸센 노선에 있는 터널 개수입니다.
• longest_tunnel_s : 조에츠 신칸센 노선에 있는 터널 중 가장 긴 터널의 시점
• longest_tunnel_e : 조에츠 신칸센 노선에 있는 터널 중 가장 긴 터널의 종점
• shortest_tunnel_s : 조에츠 신칸센 노선에 있는 터널 중 가장 짧은 터널의 시점
• shortest_tunnel_e : 조에츠 신칸센 노선이 있는 터널 중 가장 짧은 터널의 종점

제한

• 노선의 양 끝은 역입니다.
• 10ドル \leq L \leq 2 \times 10^{6}$
• 1ドル \leq Q \leq 10^{6}$
• 2ドル$번 쿼리는 최소 한 번 이상 등장합니다.

노트

조에츠 신칸센이 왜 이 타이밍에 뜬금없이 등장했을까?