You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

小仓鼠李华和它的 $(n-1)$ 个朋友因天资聪颖，收到了许多小学的 Offer（录取通知书）。它们作为形影不离的好朋友，想上同一所小学，于是它们将自己的 Offer 列表取了交集，随后根据小学排名筛除了一部分小学，现在还剩 $m$ 所小学。它们打算进行实地考察来比较这 $m$ 所小学的好坏，每所小学的位置可以抽象成以小仓鼠幼儿园为原点的平面直角坐标系上的点 $P_i (a_i, b_i)$。

这些小仓鼠决定从幼儿园出发前往各所小学，对于每一所小学：小仓鼠们轮流带队，每只小仓鼠都必须轮到且只轮到一次。由于没有哪只小仓鼠愿意带队走很长距离，于是有以下约定：小仓鼠们按编号 $1\sim n$ 的顺序依次带队，第 $i$ 只小仓鼠有带队参数 $l_i, r_i, \vec v_i$，表示它可以选择一个满足 $l_i \le \lambda_i\le r_i$ 的实数 $\lambda_i$，使考察队伍朝着向量 $\vec v_i$ 的方向前进大小为 $\lambda_i|\vec v_i|$ 的距离。

面对众多的选择，小仓鼠们面临着一个问题：按照这样的规则，它们不一定能到达小学。此外，它们希望知道，在保证能够到达某所小学的前提下，自己可以选择的最小 $\lambda_i$ 是多少。

Input

输入第一行三个整数 $n, m, t$（$1\le n\le 2 \times 10^5, 1 \le m\le 10^4, 0\le t \le \min\{10, n - 1\}$），其中 $n,m$ 含义见题目描述，$t$ 见输出格式。

接下来 $n$ 行：每行四个整数 $l_i, r_i, x_i, y_i$（$0\le l_i\le r_i\le 1000, -1000\le x_i, y_i\le 1000$），表示编号为 $i$ 的小仓鼠的带队参数为 $l_i,r_i,\vec v_i=(x_i,y_i)$。

接下来 $m$ 行：每行两个整数 $a_i, b_i$（$-10^9\le a_i, b_i\le 10^9$），表示每所小学的位置 $P_i (a_i, b_i)$。

Output

输出 $m$ 行，第 $k$ 行中：

第一个数表示在满足约定规则的情况下是否存在 ${\lambda_i}$ 的选择方案，使得它们能够到达第 $k$ 所小学，0 表示不存在，1 表示存在。

若存在，请在该行追加 $t$ 个小数，其中第 1 个数表示编号为 1 的小仓鼠的最小 $\lambda_1$，第 $i(2\le i\le t)$ 个数表示在前 $(i-1)$ 只小仓鼠依次取完最小 $\lambda_j$ 后自己可以取的最小 $\lambda_i$。注意，这里说的“最小”均是指：保证其后的小仓鼠存在某种选择方案，使得能够到达该所小学的前提下的“最小”。你的输出与标准答案绝对误差不超过 0.01 则判定为正确。

Examples

Sample Input 1

2 2 1
50 100 0 1
100 200 1 0
60 80
150 60

Sample Output 1

0
1 60.00