AT_abc450_e [ABC450E] Fibonacci String

文字列 $ X,Y $ が与えられます。文字列の列 $ S_1,S_2,\dots $ を以下で定義します。 - $ S_1=X $ - $ S_2=Y $ - $ i\geq 3 $ のとき、 $ S_i $ は $ S_{i-1} $ と $ S_{i-2} $ をこの順に連結したもの 各 $ i=1,2,\ldots,Q $ について以下の問題に答えてください。 問題：整数 $ L_i,R_i $ と文字 $ C_i $ が与えられる。 $ S_{10^{18}} $ の $ L_i $ 文字目から $ R_i $ 文字目までに文字 $ C_i $ が何個含まれるか求めよ。

入力は以下の形式で標準入力から与えられる。 > $ X $ $ Y $ $ Q $ $ L_1 $ $ R_1 $ $ C_1 $ $ L_2 $ $ R_2 $ $ C_2 $ $ \vdots $ $ L_Q $ $ R_Q $ $ C_Q $

$ Q $ 行出力せよ。 $ i $ 行目には $ S_{10^{18}} $ の $ L_i $ 文字目から $ R_i $ 文字目までに文字 $ C_i $ が何個含まれるかを出力せよ。

### Sample Explanation 1 $ S_3,S_4,S_5 $ はそれぞれ`ba`, `bab`, `babba` となります。 $ S_{10^{18}} $ は `babbababbabba...` であり、その $ 2 $ 文字目から $ 7 $ 文字目に `a` は $ 3 $ 個含まれます。 ### Constraints - $ X,Y $ は英小文字からなる長さ $ 1 $ 以上 $ 10^4 $ 以下の文字列 - $ 1 \leq Q \leq 10^5 $ - $ 1 \leq L_i \leq R_i \leq 10^{18} $ - $ C_i $ は英小文字 - 与えられる数値は全て整数