Грэгд $a= a_1 , a_2 , a_3… a_n$ массив болон $m$ үйлдэл байв.Үйлдэл болгон $l_i , r_i , d_i$ ($1≤l_i ≤r_i≤n$) –г ажигдладаг ба $i$-р үйлдэлийг хийнэ гэдэг нь $l_i, l_i +1,... r_i$ элементтэй массивын бүх гишүүдийг $d_i$ аар нэмэгдүүлнэ гэсэн үг. Грэг цаасан дээр K ширхэг асуултын тэмдэг бичnв.Асуултын тэмдэг болгон дараах хэлбэртэй : $x_i, y_i$, ($1 ≤ x_i ≤ y_i ≤ m$).Энэ нь аль 1 асуултын тэмдгийг массивруу $x_i, x_i + 1, ..., y_i$ элемэнттэй үйлдлээр оруулна гэсэн үг. Бүх асуултын тэмдэг дуусахад а массивд ямар өөрчлөлт орох вэ ?

Оролт

Эхний мөрөнд бүхэл $n , m , k$ ($1 ≤ n, m, k ≤ 10^5$)-г агуулна. 2-р мөрөнд бүхэл n $a_1, a_2, ..., a_n$ ($0 ≤ a_i ≤ 10^5$)-г агуулна – эхний массив Дараагийн m мөр нь үйлдлүүдийг агуулах ба $i$-дугаар мөр нь 3 бүхэл тоо $l_i, r_i, d_i$, ($1 ≤ l_i ≤ r_i ≤ n$), ($0 ≤ d_i ≤ 10^5$) хэлбэрээр бичигдэнэ. Дараагийн k мөр нь асуултын тэмдгүүдийг агуулах ба $i$-дах асуултын тэмдэг нь 2 бүхэл тоо $x_i$, $y_i$, ($1 ≤ x_i ≤ y_i ≤ m$) хэлбэрээр бичигдэнэ. Мөрнүүдэд байгаа тоонууд зайгаар тусгаарлагдсан байна.

Гаралт

Бүх асуултын тэмдэг дууссаны дараа энгийн мөрөнд $n$ ширхэг бүхэл тоог хэвлэнэ $a_1, a_2, ..., a_n$ . Хэвлэсэн тоонууд хоорондоо зайтай байна.

[Орчуулга хяналт хийгдээгүй. ^_^ ... Codeforces Mongolian Translation Team]