A certain gacha addicted person decides to make ~a_i~ wishes in their favourite gacha game every day for ~N~ consecutive days. However, they want to make ~Q~ queries to figure out how many wishes they have made in a given range of days in ~N~. Finally, they also want to find the number of guaranteed 5 stars (every 90 wishes) and 4 stars (every 10 wishes), respectively, that they would have already pulled from the beginning to this point.

Input Specification

The first line will contain two space-separated integers ~N~ ~(1 \le N \le 10^3)~ and ~Q~ ~(1 \le Q \le 10^5)~.

The second line will contain ~N~ space-separated integers ~a_1,a_2,...,a_n~ ~(0 \le a_i \le 10^3)~.

The next ~Q~ lines will contain two space-separated integers ~a~ and ~b~ ~(1 \le a \le b \le N)~, representing the range of days, inclusive.

Output Specification

Print out ~Q~ lines of output with three space-separated integers, representing the sum of wishes in the range ~[a,b]~, the number of guaranteed 5 stars in the range ~[1,b]~, and the number of guaranteed 4 stars in the range ~[1,b]~.

Sample Input

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

Sample Output

4 0 0
5 0 1
25 0 2