A. Card Show
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

George is a student with an absurd memory. Recently he created a way to show his abilities, using N complete decks of cards.

First, the N decks are put on a line, and are numbered from 0 to N - 1. At first each deck is ordered in the usual way, first by suit (Spade, Heart, Club and then Diamond) and the by figures (ace, two, three, ..., ten, jack, queen and king). Cards in each deck are numbered from 0 to 51, from bottom to top, being 0 the Ace of Spades, 15 the three of Hearts, and 51 the King of Diamond.

To show his abilities, George, blindfolded, plans to ask a volunteer from the crowd to do some of the following queries:

  • Shuffle: The volunteer announces 4 integers A, B, I and J and then swaps the card I with card J from all decks numbered from A to B.
  • Sum: The volunteer announces two integers A and B, computes the sum of the figures of the top cards (with number 51) from all decks numbered from A to B, writes the result on a piece of paper and shows the crowd.

The volunteer will make some sequence of those queries and, to show his abilities, after each Sum query, George will announce the result to the crowd and they will check if it matches the one computed by the volunteer.

As George wants to practice before doing the show to a real crowd, he wants you to write a program that, given a sequence of Shuffle and Sum queries, print the result of each Sum query.

Input

The first line has a single integer T, the number of test cases.

The first line of each test case has two integers N and Q, the number of decks and the number of queries. Each of the next Q lines contains a query, it begins with 0 for a Shuffle query, followed by four integers A, B, I and J; or 1 for a Sum query, followed by two integers A and B.

Limits

  • 1 ≤ T ≤ 103
  • 1 ≤ T·N ≤ 5·104
  • 1 ≤ T·Q ≤ 5·104
  • There is at least one Sum query per testcase
  • 0 ≤ A ≤ B < N
  • 0 ≤ I, J < 52 and I ≠ J
Output

For each Sum query, print the answer in a single line.

Example
Input
2
10 6
1 0 9
1 5 5
0 0 4 51 0
1 0 9
0 5 9 51 1
1 0 9
8 3
0 2 3 51 48
0 0 5 51 49
1 1 3
Output
130
13
70
15
33