Дат је низ од \(N\) функција \(F_1(x), F_2(x), \dots, F_N(x)\). Ове функције су описане помоћу два низа \(T_1, T_2, \dots, T_N\) и \(K_1, K_2, \dots, K_N\) од по \(N\) целих бројева.

• \(F_i(x) = \left\{\begin{array}{lr}min(x, K_i) , & T_i = 1\\ max(x, K_i), & T_i = 2\\ x + K_i, & T_i = 3 \end{array}\right\}\)

Потребно је одговорити на \(Q\) упита, где је \(i\)-ти упит описан са бројевима \(L_i\), \(R_i\) и \(X0_i\). Одговор на упит је:

• \(F_{L_i}(X0_i) + F_{L_i + 1}(F_{L_i}(X0_i)) + \dots + F_{R_i}(F_{R_i - 1}(\dots F_{L_i + 1}(F_{L_i}(X0_i)) \dots))\)

Опис улаза

У првом реду стандардног улаза налази се број \(N\). У другом реду стандардног улаза налази се \(N\) целих бројева, \(i\)-ти од њих је \(T_i\). У трећем реду стандардног улаза налази се \(N\) целих бројева, \(i\)-ти од њих је \(K_i\). У четвртом реду стандардног улаза налази се број \(Q\). У наредних \(Q\) редова налази се по 3 цела броја, у \(i\)-том бројеви \(L_i\), \(R_i\) и \(X0_i\).

Опис излаза

На стандардни излаз исписати одговоре на упите, у засебним редовима.

Пример 1

Улаз

5
3 3 2 1 3
3 8 -7 -6 -6
2
1 1 4
1 4 -5

Излаз

7
4

Објашњење

• \(F_1(x) = x + 3\)
• \(F_2(x) = x + 8\)
• \(F_3(x) = max(x, -7)\)
• \(F_4(x) = min(x, -6)\)
• \(F_5(x) = x - 6\)
• За први упит: \(F_1(4) = 7\)
• За други упит:
  • \(F_1(-5) + F_2(F_1(-5)) + F_3(F_2(F_1(-5))) + F_4(F_3(F_2(F_1(-5)))) =\)
  • \(-2 + F_2(-2) + F_3(F_2(-2)) + F_4(F_3(F_2(-2))) =\)
  • \(-2 + 6 + F_3(6) + F_4(F_3(6)) =\)
  • \(-2 + 6 + 6 + F_4(6) = -2 + 6 + 6 -6 = 4\)

Пример 2

Улаз

10
1 1 2 2 1 2 3 2 1 3
0 10 -7 -15 -13 -7 -4 4 12 -15
6
9 9 11
1 9 -7
7 7 -20
1 8 6
9 10 -2
9 10 -13

Излаз

11
-51
-24
-27
-19
-41

Ограничења

• \(1 \leq N, Q \leq 2 \times 10^{5}\)
• \(0 \leq |K_i| \leq 10^{9}\) за \(T_i \in \{ 1, 2 \}\)
• \(0 \leq |K_i| \leq 10^{6}\) за \(T_i = 3\)
• \(1 \leq L_i \leq R_i \leq N\)
• \(0 \leq |X0_i| \leq 10^{9}\)

Тест примери су подељени у пет дисјунктних група:

• У тестовима вредним 8 поена: \(N, Q \leq 10^{3}\).
• У тестовима вредним 20 поена: \(T_i = 3\) за све \(1 \leq i \leq N\).
• У тестовима вредним 20 поена: \(T_i = 1\) за све \(1 \leq i \leq N\).
• У тестовима вредним 24 поена: \(N, Q \leq 4 \times 10^{4}\).
• У тестовима вредним 28 поена: Без додатних ограничења.