阿源的田地 4

題目敘述

阿源終於賣完他的貨物了，一天又平安的過去了，感謝阿源的努力。時間過得很快，又到了要種植下一季作物的時候，這次阿源種植了$n$棵果樹排成一列，我們將樹兒們依序編號為$1~n$，剛開始這些樹高度皆為$0$，這些樹非常的奇妙，當某顆樹被陽光照射$x$分鐘時，他就會長高$x$公分，而陽光一次會照射一個區間的樹，現在阿源想隨時知道某顆樹現在長的多高，以便監控這些樹的生長狀態。現在總共有$q$次事件，每次事件可能有兩種: 第一種為陽光照射編號$l$到$r$這個區間的樹$x$分鐘，我們會以 $1 l r x$來代表第二種為阿源想知道編號$x$這個樹的高度(公分)，我們以 $2 x$來代表對於每個第二種事件，請輸出所詢問的樹的高度。

輸入說明

輸入的第一行包含一個正整數 $T(T\leq 10)$，代表接下來有 $T$ 個測試資料。每筆測試資料第一行會有兩個正整數 $n(n\leq 1000000)$ 及 $q(q\leq1000000)$ ，分別代表有$n$顆樹及$q$次事件，每顆樹剛開始高度都為0。接下來每次事件會有兩種形式。 $1 l r x$ 代表$l$到$r (1 \leq l\leq r \leq n)$ 這個區間的樹 $x(1\leq x \leq 1e9)$分鐘 $2 x$ 代表阿源想知道$x(1\leq x\leq n)$這顆樹的高度

輸出說明

對於每次第二種詢問，請輸出一個整數代表樹的高度

範例輸入

範例輸出

範例解釋

全部樹的高度一陽光照射的順序變化如下

$0,0,0,0,0,0,0,0,0,0$

$1,1,1,1,1,1,1,1,1,1$

$1,6,6,1,1,1,1,1,1,1$

$1,6,6,7,7,7,7,1,1,1$

$1,6,15,16,16,16,7,1,1,1$

$2,7,16,17,17,17,8,2,2,2$

子題一[10%]

$n \leq 1000,q \leq 1000$

子題二[10%]

$n \leq 1000,q \leq 1000000$

子題三[20%]

所有第一種事件都在第二種事件前發生

$ 子題四[40%]

$n \leq 100000,q \leq 100000$

子題五[20%]

$n \leq 1000000,q \leq 1000000$

Judge Setting

run-time limit: 20000 ms
memory limit: 100048576 byte
測資數量: 6