AT_abc280_h [ABC280Ex] Substring Sort

[problemUrl]: https://atcoder.jp/contests/abc280/tasks/abc280_h $ N $ 個の文字列 $ S_1,S_2,\ldots,\ S_N $ が与えられます。 $ M\ =\ \displaystyle\sum_{i=1}^N\ \frac{|S_i|(|S_i|+1)}{2} $ とおきます。 また、文字列 $ S $ と整数 $ L,\ R $ に対し、$ S[L,\ R] $ で $ S $ の $ L $ 文字目から $ R $ 文字目までの文字からなる部分文字列を表します。 整数の三つ組からなる長さ $ M $ の列 $ ((K_1,\ L_1,\ R_1),\ (K_2,\ L_2,\ R_2),\ \ldots,\ (K_M,\ L_M,\ R_M)) $ は以下の条件をみたします： - $ M $ 個の要素は相異なる。 - すべての $ 1\ \leq\ i\ \leq\ M $ に対して、$ 1\ \leq\ K_i\ \leq\ N $ かつ $ 1\ \leq\ L_i\ \leq\ R_i\ \leq\ |S_{K_i}| $ である。 - すべての $ 1\ \leq\ i\ \leq\ j\ \leq\ M $ に対して、辞書順で $ S_{K_i}[L_i,\ R_i]\ \leq\ S_{K_j}[L_j,\ R_j] $ である。 $ 1 $ 以上 $ M $ 以下の整数 $ Q $ 個 $ x_1,x_2,\ldots,\ x_Q $ が与えられます。各 $ 1\ \leq\ i\ \leq\ Q $ に対して、$ (K_{x_i},\ L_{x_i},\ R_{x_i}) $ としてあり得るものを $ 1 $ つずつ求めてください。なお、条件をみたす三つ組の列が必ず $ 1 $ つ以上存在することが証明できます。条件をみたす三つ組が複数存在する場合、どれを出力しても構いません。また、異なる $ x_i $ の間で、条件をみたす三つ組の列が共通のものである必要もありません。 辞書順とは $ 2 $ つの文字列 $ S,\ T $ が以下の条件のいずれかをみたすとき、かつそのときに限り、辞書順で $ S\ \leq\ T $ であると言います。 - $ |S|\ \leq\ |T| $ かつ $ S\ =\ T[1,\ |S|] $ である。 - ある $ 1\leq\ k\leq\ \min(|S|,\ |T|) $ が存在し、$ 1\leq\ i\leq\ k-1 $ について、$ S $ と $ T $ の $ i $ 文字目は等しく、$ S $ の $ k $ 文字目は $ T $ の $ k $ 文字目よりアルファベット順で真に小さい。

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ \lvert\ S_i\rvert\ \leq\ 10^5 $ - $ \displaystyle\sum_{i=1}^N\ \lvert\ S_i\rvert\leq\ 10^5 $ - $ 1\ \leq\ Q\ \leq\ 2\times\ 10^5 $ - $ 1\ \leq\ x_1\