Fair Inc. 的管理层决定晋升最优秀的员工，并将晋升人数限制在一个固定的区间 $[A, B]$ 内。董事会对员工的表现进行了评估，评估结果形成了一套员工之间一致的优先关系，晋升时必须遵守该关系。这意味着，对于每一对员工 $x$ 和 $y$，如果 $x$ 的表现优于 $y$，那么只有在 $x$ 被晋升的情况下，$y$ 才可能被晋升。

为了了解目前收集的数据是否足以确保公平，执行主席想要知道：

• 在区间端点（即晋升人数为 $A$ 时，以及晋升人数为 $B$ 时），有多少名员工肯定会被晋升。
• 有多少名员工完全没有被晋升的可能（即使晋升人数为 $B$ 时）。

考虑图中所示的例子。共有七名员工和八条优先规则。从员工 $x$ 指向员工 $y$ 的箭头表示 $x$ 的表现优于 $y$。晋升人数限制在区间 $[3, 4]$ 内。因此：

• 如果只有 3 个晋升名额，被晋升的员工必须是：
  • Anne、Bob 和 Greg，
  • 或者 Anne、Eve 和 Greg。 在这种情况下，有两名员工（Anne 和 Greg）肯定会被晋升。请注意，根据目前的信息，Bob 和 Eve 可能获得晋升，也可能不会。
• 如果只有 4 个晋升名额，被晋升的员工必须是：
  • Anne、Bob、Eve 和 Greg。 因此，在 4 个晋升名额的情况下，有四名员工（Anne、Bob、Eve 和 Greg）肯定会被晋升，而三名员工（Cora、Dan 和 Fred）完全没有被晋升的可能。

任务

编写一个程序，给定晋升人数的区间、员工集合以及他们之间的优先关系，计算出在每个区间端点下，肯定会被晋升的员工人数，以及完全没有被晋升可能的员工人数。

优先关系是一致的，即如果员工 $x$ 的表现优于员工 $y$，则 $y$ 不会（直接或间接地）优于 $x$。

输入格式

输入的第一行包含四个用空格分隔的整数：$A, B, E$ 和 $P$。$A$ 和 $B$ 是区间端点，$E$ 是员工人数，$P$ 是优先规则的数量。员工由 $0$ 到 $E - 1$ 之间的整数标识。

接下来的 $P$ 行，每行包含两个不同的用空格分隔的整数 $x$ 和 $y$，表示员工 $x$ 的表现优于员工 $y$。

数据范围

$1 \le A < B < E$ $2 \le E \le 5\,000$ $1 \le P \le 20\,000$

输出格式

输出包含三行。第一行包含晋升人数为 $A$ 时肯定会被晋升的员工人数。第二行包含晋升人数为 $B$ 时肯定会被晋升的员工人数。第三行包含完全没有被晋升可能的员工人数（即使晋升人数为 $B$ 时）。

样例

输入格式 1

3 4 7 8
0 4
1 2
1 5
5 2
6 4
0 1
2 3
4 5

输出格式 1

2
4
3