矩阵论

It is my experience that proofs involving matrices can be shortened by 50% if one throws the matrices out.
                                                                    
——Emil Artin



出题人特别喜欢收集各种各样特殊的矩阵，到了一年一度的校赛，当然要拿出一个矩阵和大家分享

大家都知道如何计算一个矩阵的$k$次幂，而现在出题人想考考大家如何算出某个特殊矩阵的$k$次幂的某个特定位置的值

给定一个特殊的$n$阶矩阵$A$: $\left( \begin{array}{1}a_{11} & a_{12} &a_{13} & \cdots & a_{1\ n-1}&a_{1n} \\ a_{21} & a_{22} &a_{23} & \cdots & a_{2\ n-1} & a_{2n} \\a_{31} & a_{32} &a_{33} & \cdots & a_{3\ n-1} & a_{3n} \\ \vdots & \vdots &\vdots & \ddots & \vdots & \vdots \\ a_{n-1\ 1} & a_{n-1\ 2} & a_{n-1\ 3} & \cdots & a_{n-1\ n-1}& a_{n-1\ n} \\ a_{n1} & a_{n2} & a_{n3} & \cdots & a_{n\ n-1}& a_{nn} \end{array}\right)_{n\times n}$，只有$a_{i\ i+1}$为非$0$值，其余所有位置的值全是$0$，即$A$ = $\left( \begin{array}{1} 0 & a_{12} & 0 & \cdots & 0 & 0 \\ 0 & 0 &a_{23} & \cdots & 0 & 0 \\ 0 & 0 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots &\vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 0 & a_{n-1\ n} \\ 0 & 0 & 0 & \cdots & 0 & 0\end{array}\right)_{n\times n}$，现在有$q$次询问，每次询问给出三个正整数$k_j, r_j, c_j$，对于每次询问，需要输出$\log_2 A^{k_j}_{r_jc_j} $，其中 $A^{k_j}_{r_jc_j}$表示$A$的$k_j$次幂的第$r_j$行$c_j$列上的元素值，如果$A^{k_j}_{r_jc_j} = 0$则输出$-1$

多组数据，第一行一个正整数T，表示数据组数

对于每组数据，第一行两个正整数$n, q$

接下来一行有$n-1$个正整数，分别表示$a_{12},\cdots,a_{n-1\ n}$

最后$q$行，每行三个正整数$k_j,r_j,c_j$

$1\le T\le 5，2\le n \le 10^5，1\le q \le 10^5，0\le k_j \le 10^9$

$1\le r_j, c_j \le n$

$1 \le a_{i\ i+1} \le 2^{30} (1\le i < n)$，且保证$a_{i\ i+1}$是$2$的整数次幂

对于每组数据，输出$q$行，每行一个整数，分别表示每次询问的答案

注意：不要输出浮点数

1
4 3
1 4 2
3 1 4
2 1 3
998244353 2 3

3
2
-1

"文远知行杯"杭州电子科技大学第二十一届程序设计竞赛