题目背景

唉，转生竞吧！

题目描述

如果你不了解生物的遗传学知识，可以阅读以下部分：

每个生物 M 都有两个属性，记属性一为 $X\in\{A,a\}$，属性二为 $Y\in\{A,a\}$，称 $XY$ 为其基因型，包括 $AA,Aa,aa$ 三种，这里认为 $Aa$ 和 $aA$ 等价。

对于生物 M 可患的遗传病 I，若 I 为隐性遗传病，则该生物患病当且仅当其基因型为 $aa$，若 I 为显性遗传病，则该生物患病当且仅当其基因型为 $Aa$ 或 $AA$。

若基因型为 $X_1Y_1$ 和 $X_2Y_2$ 的生物交配，则其后代的基因型有四种情况：$X_1X_2,X_1Y_2,Y_1X_2,Y_1Y_2$，且每种情况的概率相同，均为 $\dfrac{1}{4}$。

若 $A$ 的基因频率为 $p$，则认为在没有其他条件的影响下（在本题中“其他条件”包括“知道其父母”），一个生物 M 的两个属性各自有 $p$ 的概率为 $A$，$1-p$ 的概率为 $a$，且相互独立。

现在有一种生物 M 可患的遗传病 I，已知其是显性还是隐性，$A$ 的基因频率为 $p$。

否则，你可以阅读以下部分：

现在有一种和生物 M 有关的遗传病 I，已知其是显性还是隐性，其受一对常染色体等位基因 $(A,a)$ 控制，该基因的遗传符合孟德尔遗传规律，不考虑基因突变、染色体变异，交叉互换等特殊情况。

已知 $A$ 的基因频率是 $p$，即认为在没有其他条件的影响下（在本题中“其他条件”包括“知道其父母”），一个生物 M 的两个基因各自有 $p$ 的概率为 $A$，$1-p$ 的概率为 $a$，且相互独立。

现在有 $n$ 个生物 M，第 $i$ 个生物的父亲为 $fa_i$，母亲为 $mo_i$，若 $fa_i=0$ 或 $mo_i=0$ 则表示父亲或母亲未知。为了简化问题，保证 $fa_i$ 和 $mo_i$ 要么均为 $0$，要么均不为 $0$，且恰有一个生物 M 没有孩子，其余生物 M 恰有一个孩子。

给出 $n$ 个生物的关系，已知部分生物的患病情况，你需要分别求出每一个生物基因型为 $AA,Aa,aa$ 的概率，对 $10^9+7$ 取模。

你可以参见样例解释以更好的理解这个题目。

保证数据合法且保证数据随机生成。

输入格式

第一行输入四个整数 $n,t,a,b$，$n$ 表示生物总数，$t = 0$ 表示疾病 I 为隐性，$t = 1$ 表示疾病 I 为显性，$A$ 的基因频率 $p=\dfrac{a}{b}$。

接下来 $n$ 行，第 $i$ 行首先输入一个整数 $k_i$，若 $k_i=0$ 表示第 $i$ 个生物患病，$k_i=1$ 表示不患病，$k_i=2$ 表示患病状况未知。再输入两个整数 $fa_i,mo_i$ 分别表示其父亲、母亲的编号，若编号为 $0$，则表示父母未知。

输出格式

输出 $n$ 行，其中的第 $i$ 行输出三个整数，分别表示第 $i$ 个生物基因型为 $AA,Aa,aa$ 的概率，结果对 $10^9+7$ 取模。

3 0 1 2
2 0 0
0 0 0
1 1 2

500000004 500000004 0
0 0 1
0 1 0

提示

【样例解释】

记第 $i$ 个生物为 $M_i$，其基因型为 $S_i$。由于 $M_2$ 患隐性遗传病，所以 $S_2=aa$ 且 $M_3$ 含有基因（属性）$a$。又因为 $M_3$ 不患病，所以 $S_3=Aa$。

因为 $M_1$ 和患病的 $M_2$ 生出不患病的 $M_3$，所以 $M_1$ 一定不患病。因为 $p=\dfrac12$，所以对于一个随机的不患病的个体，其基因型为 $AA$ 和 $Aa$ 的概率之比为：

$$\left(\dfrac12\times\dfrac12\right):\left(2\times\dfrac12\times(1-\dfrac12)\right)=1:2 $$

又因为基因型为 $AA$ 和 $aa$ 的个体生出 $Aa$ 个体的概率为 $1$，基因型为 $Aa$ 和 $aa$ 的个体生出 $Aa$ 个体的概率为 $\dfrac12$，所以 $S_1$ 为 $AA$ 和 $Aa$ 的概率之比为：

$$\left(\dfrac13\times1\right):\left(\dfrac23\times\dfrac12\right)=1:1 $$

所以 $S_1$ 为 $AA$ 和 $Aa$ 的概率相同，均为 $\dfrac12$。

【数据范围】

本题采用捆绑测试。

子任务编号	特殊性质	分值
$0$	$n\leq5$	$15$
$1$	任意 $i\in[1,n]$ 满足 $k_i=2$
$2$	$n\leq 5\times 10^3$	$30$
$3$	无	$40$

对于 $100\%$ 的测试数据，保证：$1\leq fa_i,mo_i\leq n \leq10^5$，$t\in\{0,1\}$，$1\leq a< b\leq 10^9$，$k_i\in\{0,1,2\}$，保证出现题目给出情况的概率在模 $10^9+7$ 意义下不为 $0$，保证数据随机生成。