누적 프뤼퍼 코드

트리는 노드 $n$개와 무방향 간선 $n-1$개로 이루어진 그래프로, 어떤 두 노드든 정확히 하나의 경로로 이어진다. 라벨 트리에서는 각 노드에 $1$부터 $n$까지의 서로 다른 정수가 라벨로 붙는다.

라벨 트리의 프뤼퍼 코드는 노드가 두 개만 남을 때까지 노드를 하나씩 지우면서 만드는 수열이다. 매 단계에서 라벨이 가장 작은 잎을 지우고, 그 잎의 유일한 이웃의 라벨을 코드 끝에 덧붙인다. 잎은 이웃이 정확히 하나인 노드다. 따라서 라벨 트리의 프뤼퍼 코드는 길이가 $n-2$인 정수 수열이고, 이 코드에서 원래 트리를 복원할 수 있다.

깊이가 $k$인 완전 이진 트리 $C_k$는 노드가 $2^k - 1$개인 라벨 트리로, $j < 2^{k-1}$인 모든 $j$에 대해 노드 $j$가 노드 $2j$, $2j+1$과 이어져 있다. $C_k$의 프뤼퍼 코드를 $p_1, p_2, \ldots, p_{2^k-3}$이라고 하자.

$C_k$의 프뤼퍼 코드는 매우 길어질 수 있으므로 코드 자체를 출력하지는 않는다. 대신 코드의 일부 원소의 합을 묻는 질문 $q$개에 답해야 한다. 각 질문은 정수 $a$, $d$, $m$ 세 개로 이루어지고, 답은 $p_a + p_{a+d} + p_{a+2d} + \cdots + p_{a+(m-1)d}$이다.

첫째 줄에 완전 이진 트리의 깊이 $k$와 질문의 개수 $q$가 주어진다 ($2 \le k \le 30$, $1 \le q \le 300$). 다음 $q$개 줄에는 줄마다 질문 하나가 양의 정수 $a_j$, $d_j$, $m_j$ 세 개로 주어진다. $a_j$, $d_j$, $a_j + (m_j - 1)d_j$는 모두 $2^k - 3$ 이하다.

$q$개 줄을 출력한다. $j$번째 줄에는 $j$번째 질문의 답을 정수 하나로 출력한다.

$C_3$의 프뤼퍼 코드를 만들 때 노드는 4, 5, 2, 1, 6 순서로 지워진다. 따라서 $C_3$의 프뤼퍼 코드는 2, 2, 1, 3, 3이다.