Background

Description

二维平面上有 $n$ 个物品，第 $i$ 个物品的坐标为 $(x_i,y_i)$，黄金矿工位于原点 $(0,0)$。

对于第 $i$ 个物品，抓取需要的时间为 $t_i$，获得的分数为 $w_i$。抓取物品 $i$ 的时候，若黄金矿工与该物品的连线上还存在没有被抓取的物品，黄金矿工只能先把没有被抓取的物品全部抓取，才能抓取物品 $i$。

为了简化问题，黄金矿工抓取物品后等待钩爪旋转到下一个想要抓取的物品方向的时间忽略不计。

黄金矿工给出 $q$ 组询问，每个询问给出如下信息：

• $x\ y\ t\ w$，表示加入一个坐标为 $(x,y)$，抓取时间为 $t$，获得分数为 $w$ 的物品。

同时黄金矿工认为普通地抓取物品太无聊了，因此他向神秘商人要来了一种力量药水，使得他一次抓取就可以获得物品 $i$ 及黄金矿工与该物品连线上的所有物品，需要的时间为这些物品中抓取时间的最大值，获得的价值为这些物品的价值之和。

最后，黄金矿工想要知道使用力量药水但只抓取一次获得 $W$ 至少需要多少时间或不使用力量药水但是可以抓取任意次 $T$ 的时间最多能获得多少价值。

每一组询问之间独立，每一组询问加入的物品不会被加入到后续的询问中去，且每次询问中被抓取的物品，在后续的询问时会被放回。

Format

Input

第一行一个正整数 $n(1\le n\le 10^5)$ 表示物品数。

接下来 $n$ 行，每行四个整数分别表示一个物品的 $x(|x|\le 10^9)$ 坐标，$y(-10^9\le y<0)$ 坐标，抓取需要的时间 $t(1\le t\le 60)$，获得的分数 $w(-10^9\le w\le 10^9)$。

第 $n+2$ 行一个正整数 $q$ 表示询问次数。

接下来 $q$ 组询问，对于每组询问：

第一行四个整数分别表示加入的物品的 $x(|x|\le 10^9)$ 坐标，$y(-10^9\le y<0)$ 坐标，加入的物品抓取需要的时间 $t(1\le t\le 60)$，获得的分数 $w(-10^9\le w\le 10^9)$。

第二行两个整数表示一次询问内容：

• $1\ W(1\le W\le 10^{12})$，表示询问使用力量药水但只抓取一次获得 $W$ 至少需要多少时间。
• $2\ T(1\le T\le 60)$ 表示询问不使用力量药水但是可以抓取任意次 $T$ 的时间最多能获得多少价值。

Output

Samples

123 500

623

Note

牛客小白月赛 F

2025 zstu 校赛 hard