「Nhk R2」大户爱的驿站

题号：NC259943
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

大户爱开了 $N$ 家驿站，第 $i$ 家驿站在数轴的 $x_i$ 位置，海拔为 $h_i$ 。每家驿站有收件处和发件处，一个东西可以从第 $i$ 家驿站的发件处运到第 $j$ 家驿站的收件处，即存在 $i$ 到 $j$ 的驿路，当且仅当 $x_i>x_j$ 且 $h_i>h_j$ 。

现在有两大快递机构要垄断收发件业务，具体地，每一条驿路 $(i,j)$ 表示以 $i$ 的发件口为起点，以 $j$ 的收件口为终点，一定会被这两大快递机构其一垄断。

设 $a_{0,i}$ 表示从第 $i$ 家驿站的发件处为起点的驿路有 $a_{0,i}$ 条被第一家快递机构垄断， $a_{1,i}$ 表示从第 $i$ 家驿站的收件处为终点的驿路有 $a_{1,i}$ 条被第一家快递机构垄断， $b_{0,i}$ 表示从第 $i$ 家驿站的发件处为起点的驿路有 $b_{0,i}$ 条被第二家快递机构垄断， $b_{1,i}$ 表示从第 $i$ 家驿站的收件处为终点的驿路有 $b_{1,i}$ 条被第二个快递机构垄断。

大户爱不希望得罪任何一个快递机构，所以她希望 $\sum_{i=1}^{N}|a_{0,i}-b_{0,i}|+|a_{1,i}-b_{1,i}|$ 最小。

大户爱有 $Q$ 个询问，每次询问会独立地（即每次询问不会影响到后面的询问）新开一家驿站，设为第 $N+1$ 家驿站。给出这个驿站的位置 $x_{N+1}$ 和海拔 $h_{N+1}$ ， $a_{0,N+1},a_{1,N+1},b_{0,N+1},b_{1,N+1}$ 的定义同上，求最小的 $\sum_{i=1}^{N+1}|a_{0,i}-b_{0,i}|+|a_{1,i}-b_{1,i}|$ 。

输入描述:

第一行两个正整数 。

接下来  行每行两个数  和 。

接下来  行每行两个整数 。

输出描述:

 行，每行一个整数表示当前询问的答案。

示例1

输入

复制

输出

复制

4
2
4

备注:

对于  的数据，满足 。