Distribute Pages in Books

You are given n books, each with an initial number of pages. You must process q queries of two types:

• Type 1: The query is given as 1 p k. Distribute k pages uniformly among the first p books. That is, each of the first p books receives \(\lfloor k/p \rfloor\) additional pages.
• Type 2: The query is given as 2 p. Output the sum of pages in the first p books.

Process the queries in the order given, updating the number of pages for each distribution query, and printing results for the sum queries.

inputFormat

The first line contains two integers n and q, where n is the number of books and q is the number of queries.

The second line contains n space-separated integers representing the initial number of pages in each book.

The next q lines each contain a query. For a Type 1 query, the line contains three integers: 1 p k, which means distribute k pages among the first p books (each gets \(\lfloor k/p \rfloor\) pages). For a Type 2 query, the line contains two integers: 2 p, and you must output the sum of pages in the first p books.

outputFormat

For each query of Type 2, print the resulting sum on a new line.

## sample

5 5
10 20 30 40 50
1 3 15
2 3
1 4 8
2 4
2 5

75
123
173

</p>