공통 구간 분해 트리

크기가 $N$인 순열 $P_0, P_1, \cdots, P_{N-1}$가 주어질 때, 이 순열에 대응하는 공통 구간 분해 트리를 출력한다. 이 문제에서 사용하는 용어는 다음과 같이 정의한다.

• 구간은 어떤 정수 $l$와 $r$ ($\ 0 \leq l \leq r <N$)에 대해 $\lbrace i\in \mathbb{Z}\ |\ l \leq i \leq r\rbrace$로 나타낼 수 있는 집합이다. 이러한 구간을 구간 \[l, r\]로 표기한다.
• 연결 구간은 $\lbrace P_i\ |\ l \leq i \leq r\rbrace$도 구간인 구간 \[l, r\]이다.
• 강한 구간은 모든 연결 구간 $J$에 대해 $I \subset J$, $J \subset I$, $I \cap J =\emptyset$ 중 하나가 성립하는 연결 구간 $I$이다.
• 공통 구간 분해 트리는 포함 관계에 따른 부분 순서에서 모든 강한 구간의 하세 도표로 표현되는 루트 트리이다.
• 선형 노드는 그 자식들을 왼쪽 끝점 $l$의 오름차순으로 배열했을 때, 연속한 임의의 자식들의 합집합이 연결 구간을 이루는 정점이다.
• 소수 노드는 선형 노드가 아닌 정점이다.

제약 조건

• $1 \leq N \leq 500000$
• $0 \leq P_i < N$
• $P_i \neq P_j (i \neq j)$

$N$
$P_0\ P_1\ P_2\ \cdots P_{N-1}$

$X$
$p_0\ l_0\ r_0\ S_0$
$p_1\ l_1\ r_1\ S_1$
$\vdots$
$p_2\ l_{X-1}\ r_{X-1}\ S_{X-1}$

$X$는 공통 구간 분해 트리의 정점 수이다. $p_i$( $p_i < i$ )는 $i$번째 정점의 부모인 정점에 부여된 정수이며, $i$번째 정점이 트리의 루트라면 $p_i=-1$이다. \[l_i,r_i\]는 $i$번째 정점에 대응하는 구간이며, $S_i$는 $i$번째 정점이 선형 노드이면 "linear", 소수 노드이면 "prime"이다.