Biến đổi dãy

Cho một mảng \(A[1], A[2], \ldots, A[n]\) gồm \(n\) phần tử. Bạn cần thực hiện \(m\) truy vấn để biến đổi mảng theo quy tắc sau.

Mỗi truy vấn có dạng \((L, R, v, p)\), trong đó:

• Tính số lượng các phần tử trong đoạn \(A[L], A[L+1], \ldots, A[R]\) nhỏ hơn \(v\). Gọi kết quả này là \(k\).
• Cập nhật giá trị \(A[p]\) theo công thức:
  \(A[p]\) = \(\left\lfloor \frac{u \cdot k}{R - L + 1} \right\rfloor\)
  trong đó \(\lfloor x \rfloor\) là phép chia nguyên (bỏ phần dư).

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(m\) và \(u\) \((1 \leq n, m \leq 2 \times 10^5\), \(1 \le u \le 10^9)\).
• Dòng thứ hai chứa \(n\) số nguyên \(A[1], A[2], \ldots, A[n]\) \((0 \leq A[i] \leq u)\).
• \(m\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(L, R, v, p\) \((1 \leq L \leq R \leq n, 1 \leq p \leq n, 0 \leq v \leq u)\).

Output

Sau khi thực hiện toàn bộ \(m\) truy vấn, xuất \(n\) số trên một dòng, biểu diễn giá trị cuối cùng của mảng \(A\).

Example

7 2 10
2 3 2 9 8 2 8
3 6 9 2
2 4 1 3

2
7
0
9
8
2
8

Scoring

• Có \(20\%\) số điểm ứng với \(n, m \le 10^3\).
• \(80\%\) số điểm còn lại không có ràng buộc thêm.