Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3943
Himalayas

Time Limit: 5 Seconds      Memory Limit: 65536 KB

The Himalayas or Himalaya is a mountain range in the Indian subcontinent, which separates the Indo-Gangetic Plain from the Tibetan Plateau. This range is home to nine of the ten highest peaks on Earth, including the highest above sea level, Mount Everest. The Himalayas have profoundly shaped the cultures of South Asia. Many Himalayan peaks are sacred in both Buddhism and Hinduism.


By Sudan Shrestha. License: CC-by-sa 3.0

Edward, the headmaster of Marjar University, is doing a research about the Himalayas. To simplify the model, Edward thinks that there are N mountains in the Himalayas and they are lined up. Edward numbered them from 1 to N from left to right. What's more, Edward defines peaks of the Himalayas which satisfy:

  1. 1 < i < N
  2. Hi - 1 < Hi > Hi + 1, where Hi means the height of the i-th mountain

Then the i-th mountain is called a peak.

Furthermore, Edward found an interesting fact about the Himalayas from its history: earthquakes will change the height of some continuous mountains. To be more specific, for an earthquake, we record it as (L, R, A, B), which means the height of the i-th (LiR) mountain will change by A + (i - L) * B after the earthquake.

Edward wants to know the amount of peaks after each earthquake. Please tell him.

Input

There are multiple test cases. The first line of input contains an integer T (≤ 10) indicating the number of test case. For each test case:

The first line contains two integers N, M (1 ≤ N, M ≤ 105) indicating the number of the mountains and the number of the earthquakes.

The next line contains N (1 ≤ N ≤ 105) integers, the i-th integer is the initial height Hi of the i-th mountain (0 ≤ Hi ≤ 105).

Then followed by M lines, each line contains four integers L, R, A, B (1 ≤ LRN, 1 ≤ B ≤ 105, -105A ≤ 105) of an earthquake, in chronological order.

Output

For each earthquake, output the amount of peak after it.

Sample Input

2
4 2
1 5 3 0
3 4 1 1
3 4 2 1
4 2
1 5 3 0
3 4 1 1
3 4 1 1

Sample Output

1
1
1
0

Hint

1 5 3 0 -> 1 5 4 2 -> 1 5 6 5


Author: CHEN, Weijie
Source: The 13th Zhejiang Provincial Collegiate Programming Contest
Submit    Status