Angels and Demons

You are walking at midnight along a road that has $N$ checkpoints numbered from $1$ to $N$ from left to right. Each checkpoint may be empty, or it may have angels or demons stationed there. If a checkpoint has an angel or demon, they will cast a blessing or curse of power $D$ upon you which will be active till checkpoint $x$. This blessing or curse will be in effect at all the checkpoints $i$ for $s≤i≤x$. If you receive a blessing of power $D$, your health will increase by $D$ at each checkpoint where it is active. Conversely, if you receive a curse of power $D$, your health will decrease by $D$ at each checkpoint where it is active.

Formally, if an angel with power $D$ is stationed at checkpoint $s$ and has an endpoint at checkpoint $x$, then for each checkpoint $i$ $(s ≤ i ≤ x)$ your health will increase by $D$. On the other hand if an demon with power $D$ is stationed at checkpoint $s$ and has an endpoint at checkpoint $x$, then for each checkpoint $i$ $(s ≤ i ≤ x)$ your health will decrease by $D$.

If at any checkpoint (including checkpoint $N$) your health becomes zero or negative, you will die. What is the minimum health you need to start with, to survive the walk from checkpoint $1$ to $N$? Please note here, the initial health must always be an integer value.

Note that there may be multiple angels and/or demons stationed at some checkpoints, and angels are slightly more powerful than demons. So if both angels and demons are active at a checkpoint, then all the blessings will take effect first, followed by the curses. Please refer to the explanation of the sample for better understanding.

Input

The first line of the input will contain an integer, $T$ $(1 ≤ T ≤ 1000)$ which denotes the number of test cases.

Each of the test cases starts with two integers, $N$ $(1 ≤ N ≤ 10^9)$ and $Q$ $(1 ≤ Q ≤ 2\times10^5)$ describing the number of checkpoints and the total number of demons and angels. Then there will be $Q$ lines. Each of the next $Q$ lines will contain four integers separated by spaces in the following format describing the parameters for an angel or a demon:

• $type$ $s$ $x$ $D$ $(1 ≤ type ≤ 2;$ $1 ≤ s ≤ x ≤ N;$ $1 ≤ D ≤ 10^4)$

If $type = 1$ then it is an angel, otherwise it is a demon. $D, ~s, ~x$ describes the power of the blessing/curse and the active region of the blessing/curse.

It is guaranteed that the sum of $Q$ over all test cases $≤ 2 \times 10^5$.

Output

For each test case, output a single integer, the minimum amount of health needed to survive the walk.

Sample

Input	Output
1 10 3 2 1 3 2 1 1 2 2 1 2 3 1	1

Explanation of the sample:

You start with health 1. It can be shown that you cannot start with any integer health value lesser than this and be alive while completing the journey.

At checkpoint 1 first you get a blessing of power 2, your health becomes 3, then you get a curse of power 2 and your health drops to 1.

At checkpoint 2 first you get two blessings of power 1 and 2, your health becomes 1 + 1 + 2 = 4, then you get a curse of power 2, your health becomes 2.

At checkpoint 3, first you get a blessing of power 1, your health becomes 3, then you get a curse of power 2, your health becomes 1.

Then you continue with health 1 to checkpoint 10 to finish your journey. You didn’t die and you made it to the end! Congrats!