Se dă un șir de N numere și Q operații de tipul:

• 0 a b val : se va aduna valoarea val la toate numerele din intervalul [a, b].
• 1 a b : se va afișa elementul minim par și elementul maxim impar din intervalul [a, b]; în cazul în care unul dintre aceste numere nu există, se va afișa -1 în locul său.

Cerința

Răspundeți corect la toate operațiile de tip 1.

Date de intrare

Programul citește de la tastatură numărul N. Pe a doua linie se vor afla N numere reprezentând elementele din sir. Pe linia a treia se va afla numărul Q, iar pe următoarele Q linii se vor afla Q operații sub forma descrisa în enunț.

Date de ieșire

Se vor afișa pe ecran răspunsurile la operațiile de tip 1, câte unul pe linie.

Restricții și precizări

• N, Q <= 200.000
• Numerele din sir sunt cuprinse intre 1 și 2.000.000.000.
• Valorile val din operațiile de tip 0 sunt cuprinse intre 1 și 2.000.000.000.
• ATENȚIE! În cazul în care unul din cele două răspunsuri la o operație de tip 1 nu poate fi calculat, se va afișa -1

Exemplu:

Intrare

7
5 6 3 1 9 8 5
10
1 2 5
0 2 3 2
1 2 4
0 2 7 3
1 2 4
1 4 7
0 5 7 1
1 1 6
1 1 2
1 3 4

Ieșire

6 9
8 5
4 11
4 11
4 13
-1 11
4 -1

Explicație

Șirul inițial este: 5 6 3 1 9 8 5.
Operația 1 2 5: Se vor afișa cele doua valori cerute pe intervalul [2; 5].
Operația 0 2 3 2: Șirul nou format va fi 5 8 5 1 9 8 5.
Operația 1 2 4 : Se vor afișa cele doua valori cerute pe intervalul [2; 4].
Operația 0 2 7 3 : Șirul nou format va fi 5 11 8 4 12 11 8.
Operația 1 2 4 : Se vor afișa cele doua valori cerute pe intervalul [2; 4].
Operația 1 4 7 : Se vor afișa cele doua valori cerute pe intervalul [4; 7].
Operația 0 5 7 1 : Șirul nou format va fi 5 11 8 4 13 12 9.
Operația 1 1 6 : Se vor afișa cele doua valori cerute pe intervalul [1; 6].
Operația 1 1 2 : Se vor afișa cele doua valori cerute pe intervalul [1; 2].
Operația 1 3 4 : Se vor afișa cele doua valori cerute pe intervalul [3; 4].