文字列 \(S\) と \(T\) をこの順に連結させたものを \(S+T\) と表します。
いくつかの補題を順に示していきます。

補題 1

\(\mathtt{-++-+--+}\) の各文字を \(k\) 回ずつ繰り返して連結させた文字列を \(T_k\) と表すことにすると、\(\mathtt{+-}\) からなる任意の文字列 \(S\) に対して、以下が成り立つ。

• \(g(S+T_k)=g(S)+48k^4\)

補題 1 の証明

\(h_0(x)=\sum_{i=1}^{k}f(x+i)\) \(h_1(x)=h_0(x+k)-h_0(x)\)
\(h_2(x)=h_1(x+2k)-h_1(x)\)
\(h_3(x)=h_2(x+4k)-h_2(x)\)
と置くと、
\(g(T_k)\; =-h_0(x)+h_0(x+k)+h_0(x+2k)-h_0(x+3k)+h_0(x+4k)-h_0(x+5k)-h_0(x+6k)+h_0(x+7k)\; =h_1(x)-h_1(x+2k)-h_1(x+4k)+h_1(x+6k)\; =-h_2(x)+h_2(x+4k)\; =h_3(x)\)
です。 \(h_0(x)\) は最高次項の係数が \(k\) の三次関数です。
\(k(x+k)^3-kx^3\) の \(x^2\) の項の係数は \(3k^2\) なので、\(h_1(x)\) は最高次項の係数が \(3k^2\) の二次関数です。 同様に考えて、\(h_2(x)\) は最高次項の係数が \(12k^3\) の一次関数、\(h_3(x)\) は最高次項の係数が \(48k^4\) の定数関数です。 したがって、\(h_3(x)=48k^4\) です。

補題 2

\(\mathtt{+--+-++-}\) の各文字を \(k\) 回ずつ繰り返して連結させた文字列を \(T'_k\) と表すことにすると、\(\mathtt{+-}\) からなる任意の文字列 \(S\) に対して、以下が成り立つ。

• \(g(S+T'_k)=g(S)-48k^4\)

補題 2 の証明

補題 1 と同様に示せます。

補題 3

\(X \equiv Y \pmod{48}\) のとき、\(g(S)=X\) となる文字列 \(S\) が存在するならば \(g(S')=Y\) となる文字列 \(S'\) が存在する。

補題 3 の証明

\(S\) の後ろに \(T_1\) か \(T'_1\) をいくつか連結させると構成することができます。

補題 4

\(g(S) \equiv N \pmod {48}\) となる \(S\) が存在するならば、その中に \(|S| \leq 48^2\) となるものが存在する。

補題 4 の証明

\(g(S) \equiv N \pmod {48}\) となる \(S\) のうち \(|S|\) が最小となるものを取り、\(|S| \gt 48^2\) として矛盾を示せればよいです。
\(S\) の \(i\) 文字目までを \(S_i\) と表します。
鳩ノ巣原理より、\((|S_i| \pmod{48},g(S_i) \pmod {48})=(|S_j| \pmod{48},g(S_j) \pmod {48})\) となる \(i,j \; (0 \leq i < j \leq |S|)\) が存在します（ただし、\(g(S_0) \pmod {48}=0\) とする）。 \(S\) の \(i+1\) 文字目から \(j\) 文字目を取り除いた文字列 \(S'\) は \(g(S') \equiv N \pmod{48}\) を満たし、\(j-i \geq 48 > 2\) なので、矛盾します。

補題 5

\(|\sum_{i=1}^{48^2}f(i)| \leq 5 \times 10^{14}\)

補題 5 の証明

実際にプログラムを用いて調べるとわかります。

補題 6

\(N \leq 670\) とする。 空の数列 \(A\) を用意し、\(k=5,4,3,2,1\) の順に、以下の操作を繰り返す。

• \(N \geq k^4\) である限り \(N\) から \(k^4\) を引き、\(A\) の末尾に \(k\) を追加する。

このとき、以下が成り立つ。

• \(\sum_{i=1}^{|A|}{A_i} \leq 47\)
  

補題 6 の証明

\(k=1,2,3,4\) について、\(k^4\) が引かれる回数は高々 \(\left \lfloor \frac{(k+1)^4}{k^4} \right \rfloor\) で、この値はそれぞれ \(15,5,3,2\) です。
また、\(5^4\) が引かれる回数は高々 \(1\) 回です。 \(1 \times 15 + 2 \times 5 + 3 \times 3 + 4 \times 2+5 \times 1=47\) なので示されました。

補題 7

\(N \leq \frac{6 \times 10^{14}}{48}\) とする。 空の数列 \(A\) を用意し、\(k=\lfloor N^{\frac{1}{4}}\rfloor,\lfloor N^{\frac{1}{4}}\rfloor-1,\dots,1\) の順に、以下の操作を繰り返す。

• \(N \geq k^4\) である限り \(N\) から \(k^4\) を引き、\(A\) の末尾に \(k\) を追加する。

このとき、以下が成り立つ。

• \(\sum_{i=1}^{|A|}{A_i} \leq 2590\)
  

補題 7 の証明

\(N\) から \(k^4\) を引く時、
\(N-k^4 \leq (k+1)^4-1-k^4=4k^3+6k^2+4k \leq 4\lfloor N^{\frac{1}{4}}\rfloor^3+6\lfloor N^{\frac{1}{4}}\rfloor^2+4\lfloor N^{\frac{1}{4}}\rfloor\)
です。 これをもとに実際に計算すると、\(10\) 回引き算をすると \(N\) は \(670\) 以下になり、そのときの \(k\) の総和は \(2543\) 以下です。
補題 6 と合わせて、\(2543+47=2590\) なので示されました。

解法

\(k=L,L+1,\dots,\min(R,L+47)\) に対して、\(g(S_k) \equiv k \pmod {48}\) となる \(S_k\) が存在するかどうかを判定します。
補題 4 より、\(O(48^3)\) の dp でわかります。
存在するならば、この dp を復元して、\(g(S'_k) \equiv k \pmod{48}\) となる長さ \(48^2\) 以下の \(S'_k\) を構築できます。
補題 5 より、\(|g(S'_k) - k|\leq 6 \times 10^{14}\) です。
補題 7 によりできる \(A\) を構成し、\(i=1,2,\dots,|A|\) について \(S_k\) の末尾に \(T_{A_i}\)（または \(T'_{A_i}\)）を連結させてできる文字列を改めて \(S_k\) とすると、これは \(g(S_k)=k\) を満たします。
補題 7 より、\(|S_k| \leq 48^2+8 \times 2590=23024\) です。 \(S_k\) の末尾に \(T_1\) を適切な個数連結させることで、\(L\) 以上 \(R\) 以下の整数のうち \(48\) で割った余りが \(k\) に等しいようなものをすべて生成可能な文字列を作ることができます。
こうして \(k=L,L+1,\dots,\min(R,L+47)\) に対して、できた文字列を（\(S_k\) が存在しないならば無視して）すべて連結させれば、生成可能な文字列が存在しないような \(k\) 以外をすべて生成可能な文字列を作ることができます。
\(48 \times 23024+8 \times 10^5 = 1905152 \leq 2 \times 10^6\)
より、この文字列の長さは \(2 \times 10^6\) 以下に抑えることができます。
後半の \(l,r\) を求めるパートも適切に処理すれば求めることができます。