Саябақта солдан оңға қарай бір қатарға орналасқан және осы ретпен $0, 1, \dots, N - 1$ сандарымен нөмірленген $N$ алаң бар.
Саябақ ішінде $0, 1, \dots, N - 1$ сандарымен нөмірленген $N$ адам бар. Сіз $0$ мен $N - 1$ аралығындағы теріс емес бүтін сандардан тұратын $X = (X_1, X_2, \dots, X_{|X|})$ тізбегін жариялағанда, адамдар келесі ережелер бойынша шеру жасайды:
- Әрбір $i = 0, 1, \dots, N - 1$ үшін $i$-ші адам $i$-ші алаңға барады.
- Әрбір $j = 1, 2, \dots, |X|$ үшін осы ретпен келесі әрекет орындалады:
- Дәл қазір $X_j$ алаңында тұрмаған әрбір адам $X_j$ алаңына қарай дәл бір алаңға жылжиды.
Сізге $0$ мен $N - 1$ аралығындағы бүтін сандардан тұратын ұзындығы $M$ болатын $A = (A_0, A_1, \dots, A_{M-1})$ тізбегі берілген.
Сіз $Q$ онлайн сұранысқа жауап беруіңіз керек. Әрбір $i = 1, 2, \dots, Q$ үшін $t'_i, L'_i, R'_i, P'_i$ бүтін сандары беріледі. Алдымен келесі процедура арқылы $t_i, L_i, R_i, P_i$ мәндерін қалпына келтіріңіз:
$\text{ans}_0 = 0$ болсын, ал $\text{ans}_i$ арқылы $i$-ші сұраныстың жауабын белгілейік. $t_i, L_i, R_i, P_i$ мәндерін келесідей қалпына келтіріңіз:
- $t_i = ((t'_i + \text{ans}_{i-1}) \bmod 2)$
- $a = ((L'_i + \text{ans}_{i-1}) \bmod M)$
- $b = ((R'_i + \text{ans}_{i-1}) \bmod M)$
- $L_i = \min(a, b)$
- $R_i = \max(a, b)$
- $P_i = ((P'_i + \text{ans}_{i-1}) \bmod N)$
Мұнда теріс емес бүтін сан $a$ және оң бүтін сан $b$ үшін $(a \bmod b)$ өрнегі $a$ санын $b$-ға бөлгендегі қалдықты білдіреді, ол $0$ мен $b - 1$ аралығында жатады.
Қалпына келтірілген әрбір $(t_i, L_i, R_i, P_i)$ үшін келесі сұранысқа жауап беріңіз:
- Егер $t_i = 0$ болса: $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$ болсын. Шеруді модельдеп, $P_i$ адамы соңында тоқтайтын алаңның нөмірін шығарыңыз.
- Егер $t_i = 1$ болса: $X = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$ болсын. Шеруді модельдеп, соңында $P_i$ алаңында қанша адам болатынын шығарыңыз.
Кіріс деректер
Кіріс деректер келесі форматта беріледі:
N M Q
A_0 A_1 ... A_{M-1}
t'_1 L'_1 R'_1 P'_1
t'_2 L'_2 R'_2 P'_2
:
t'_Q L'_Q R'_Q P'_Q- Барлық кіріс мәндері — бүтін сандар.
- $1 \le N, M, Q \le 2 \times 10^5$
- $0 \le A_i \le N - 1$ ($0 \le i \le M - 1$)
- $0 \le t'_i, t_i \le 1$ ($1 \le i \le Q$)
- $0 \le L'_i, R'_i \le M - 1$ ($1 \le i \le Q$)
- $0 \le L_i \le R_i \le M - 1$ ($1 \le i \le Q$)
- $0 \le P'_i, P_i \le N - 1$ ($1 \le i \le Q$)
Шығыс деректер
$Q$ жол шығарыңыз. Әрбір $i = 1, 2, \dots, Q$ үшін $i$-ші сұраныстың жауабы $\text{ans}_i$ мәнін шығарыңыз.
Мысалдар
1-мысал кіріс
4 5 3 0 2 3 2 1 0 1 3 2 1 0 2 1 1 4 4 1
1-мысал шығыс
2 0 3
2-мысал кіріс
7 4 1 3 3 3 3 1 3 0 3
2-мысал шығыс
7
Ескертпе
1-мысалдың бірінші сұранысында $(t_i, L_i, R_i, P_i) = (0, 1, 3, 2)$ және $X = (2, 3, 2)$ болғанда, $2$-ші адам $2 \to 2 \to 3 \to 2$ ретімен жылжиды, сондықтан жауап $2$ болады.
1-мысалдың екінші сұранысында $(t_i, L_i, R_i, P_i) = (1, 2, 4, 3)$ және $X = (3, 2, 1)$ болғанда, соңында $3$-ші алаңдағы адамдар саны $0$ болады.
1-мысалдың үшінші сұранысында $(t_i, L_i, R_i, P_i) = (1, 4, 4, 1)$ және $X = (1)$ болғанда, соңында $1$-ші алаңдағы адамдар саны $3$ болады.