After a coordinate transformation \((i,\ j) \rightarrow (i-j,\ j)\), each query spans edges between \((u_i,\ k)\) and \((v_i,\ k+p_i)\) for integers \(u_i,\ v_i,\ p_i\). We can then apply another coordinate transformation \((i,\ j) \rightarrow (i,\ j+h_i)\) for an integer sequence \(h=(h_1,\ h_2,\ \dots,\ h_N)\) without affecting the contents of queries (in other words, we may shift each row horizontally).

Let us take \(h\) so that the following is satisfied.

• \(p_i=0\) if \((u_i,\ j)\) and \((v_i,\ j')\) are disconnected for every \(0 \le j,\ j' < N\) just before the \(i\)-th query \((u_i,\ v_i,\ p_i)\) adds edges.

This condition can be written as \(h_{u_i}-h_{v_i}=p'_i\) for \((u_i,\ v_i)\) in those queries. The graph with \(N\) vertices and those edges \((u_i,\ v_i)\) will be a forest, so such \(h\) always exists.

For a query \((u_i,\ v_i,\ p_i)\) that is not among the above ones, \((u_i,\ k)\) and \((v_i,\ k)\) will be already connected when adding edges, so we may assume that it adds edges between \((u_i,\ k)\) and \((u_i,\ k+p_i)\) instead.

As a result, after taking an appropriate \(h\), we have two kinds of queries:

• those that add edges between \((u_i,\ k)\) and \((v_i,\ k)\),
• those that add edges between \((u_i,\ k)\) and \((u_i,\ k+p_i)\).

After processing just the queries of the first kind, each column will have the graph \(G_{row}\): the part of \(G\) in the first column. If we then process queries of the second kind, the \(N\) columns for each connected component in \(G_{row}\) will merge into \(g\) connected components, where \(g\) is the greatest common divisor of \(N\) and the \(p_i\)’s in relevant queries.

Thus, after determining \(h\), we can process the queries by maintaining the following:

• the graph \(G_{row}\), the part of \(G\) in the first column,
• a sequence \(g\), containing the number of connected components corresponding to each connected component in \(G_{row}\),

in \(O((N+Q)\log N)\) time, using tools such as dsu.