Sone and Jie’s String Games

Sone has a mischievous pet named Jie. One day, while Sone was studying string matching problems, he left two strings on the table: a string \(a\) of length \(n\) and a string \(b\) of length \(m\). Each character of these strings is an integer in the range \(1\) to \(\Sigma\), where \(\Sigma\) is the size of the character set.

Before leaving, Sone warned Jie not to touch string \(b\) because it was very important. Consequently, Jie could only play with string \(a\).

For any string \(s\), let \(s[l:r]\) denote the substring from the \(l\)-th to the \(r\)-th character (if \(l>r\), it is the empty string). Jie defines a function for two strings \(s\) and \(t\):

[ f(s,t)=\max_{s[1:k]=t[1:k]} k ]

In other words, \(f(s,t)\) is the length of the longest common prefix of \(s\) and \(t\).

Then he defines a function \(F(a,b)\) which produces a pair \((x,y)\) where:

[ x=\max_{1\le i \le |a|} f(a[i:,|a|],b) ]

and \(y\) is the number of indices \(i\) for which \(f(a[i:\,|a|],b)=x\).

Jie performs a total of \(q\) operations. There are four types of operations:

1. Modify a single character of string \(a\) and then query \(F(a,b)\). (Note that \(a\) remains modified for subsequent operations.)
2. Select a substring \(c\) of \(a\) and query \(F(c,b)\).
3. Select two suffixes of \(b\) (specified by their starting positions) and query the length of their longest common prefix.
4. Select two substrings \(s_1\) and \(s_2\) of \(b\) and query whether their concatenation \(s_1+s_2\) is a substring of \(b\). If yes, output yes; otherwise, output no.

Input and Output Formats:

The input begins with three integers \(n\), \(m\), and \(q\). The next line contains \(n\) space-separated integers representing string \(a\). The following line contains \(m\) space-separated integers representing string \(b\). Each of the next \(q\) lines represents an operation in one of the following formats (all indices are 1-indexed):

• Operation 1 (modify and query): 1 pos new_val
• Operation 2 (query a substring of \(a\)): 2 L R
• Operation 3 (query LCP of two suffixes of \(b\)): 3 i j
• Operation 4 (check concatenation in \(b\)): 4 L1 R1 L2 R2

For operations of type 1 and 2, output two integers \(x\) and \(y\) separated by a space where \(x\) and \(y\) are defined as above. For operation type 3, output the integer representing the longest common prefix length. For operation type 4, output either yes or no.

inputFormat

The first line contains three integers \(n\), \(m\), and \(q\) — the lengths of strings \(a\) and \(b\), and the number of operations, respectively.

The second line contains \(n\) space-separated integers representing string \(a\).

The third line contains \(m\) space-separated integers representing string \(b\).

Each of the following \(q\) lines describes an operation in one of the following formats:

• 1 pos new_val
• 2 L R
• 3 i j
• 4 L1 R1 L2 R2

outputFormat

For operations of type 1 and 2, output two space-separated integers: \(x\) and \(y\), where \(x = \max_{i} f(a[i:],b)\) and \(y\) is the number of suffixes achieving \(x\).

For an operation of type 3, output a single integer: the length of the longest common prefix of the two specified suffixes of \(b\).

For an operation of type 4, output yes if the concatenated string is a substring of \(b\), otherwise output no.

sample

5 4 5
1 2 3 4 5
1 2 4 5
1 3 4
2 2 4
3 1 2
4 1 2 3 4
3 2 3

3 1
0 3
0
yes
0

</p>