시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB1213138839.618%

문제

We all love problems without a story, who doesn’t?! Here’s one more.

In this problem you are given an array of N integers a1, a2, · · · , aN. Followed by Q queries, each query will be in one of the following types:

  1. For each integer ai where L ≤ i ≤ R, replace it with floor(sqrt(ai)). Where sqrt(a) is the square root of a, and floor(b) is the integer value of b after removing everything on the right of the decimal point.
  2. Print the sum of all integers ai where L ≤ i ≤ R.
  3. Add x to each integer ai where L ≤ i ≤ R.

입력

Your program will be tested on one or more test cases. The first line of the input will be a single integer T (1 ≤ T ≤ 100) representing the number of test cases. Followed by T test cases.

Each test case starts with a line containing 2 integers separated by a space, N (1 ≤ N ≤ 105)

representing the number of integers in the array and Q (1 ≤ Q ≤ 20, 000) representing the number of queries.

Followed by a line containing N integers separated by a space, which are the initial integers in the array a1, a2, . . . , aN (1 ≤ ai ≤ 106).

Followed by Q lines, each line will be in one of the following formats (1 ≤ L ≤ R ≤ N) and (1 ≤ x ≤ 106):

  • A query of the first type: 1 L R
  • A query of the second type: 2 L R
  • A query of the third type: 3 L R x

출력

For each query of the second type, print the corresponding answer in a single line.

예제 입력 1

1
10 7
1 5 123 53 12 2901 12 1234 657 3419
2 3 7
3 5 8 1
1 2 4
3 1 6 1000
2 1 10
2 2 8
1 3 5

예제 출력 1

3101
14260
9183