Alice and Bob find out a new, cool king game to play, and they want to play the game with you. You will enjoy the game, right?

Alice and Bob will give you two integer sequences $a_1, a_2, \dots, a_N$, $w_1, w_2, \dots, w_N$ with length $N$.

Alice and Bob allow you to do the following operations for many(possibly zero) times:

• change $a_i$ to any integer, this operation will cost you $w_i$ dollars.

Now, they will give you $Q$ indepenedent queries. In the $i$-th query, they give you four integers $L_i, R_i, x_i, y_i$. They want you to make the integers $a_{L_i}, a_{L_i + 1}, \dots, a_{R_i}$ has $z$ distinct integers, such that $z \in [x_i, y_i]$. Also, since they are poor, they want you to spend as little as possible.

Please write a program to help them calculate the answers (minimum dollar that they have to spend).

小 A 和小 B 最近發現一個酷酷的國王遊戲，他們想和你一起玩。

他們會給你兩個整數序列 $a_1, a_2, \dots, a_N$, $w_1, w_2, \dots, w_N$ 長度皆為 $N$

你可以做以下操作任意多次(可以不做)

• 把 $a_i$ 改成任意整數 代價為 $w_i$ 元

現在，他們將對你詢問 $Q$ 次 (不同的詢問之間互相獨立 不影響)。 第 $i$ 次詢問，會有四個整數 $L_i, R_i, x_i, y_i$。目標是要讓 $a_{L_i}, a_{L_i+1}, \dots, a_{R_i}$ 中恰有 $z$ 個不同的整數，其中 $z \in [x_i, y_i]$。同時因為他們很窮，所以希望你花越少代價越好

請寫一個程式幫幫他們計算答案 (最少需要花多少錢)