H. Numbers of Power
time limit per test
1.5 seconds
memory limit per test
128 megabytes
input
standard input
output
standard output
Example
Input
9
5 26 2 16 20 25 33 31 3
5
1 1 9
3 1 9
1 1 9
2 1 9 11
1 2 8
Output
31
26
286