题目描述

游乐场的跷跷板以力矩相等原则判断是否平衡。即如果 (w_l d_l = w_r d_r)，则认为跷跷板是平衡的。此处，(w_l)、(w_r) 分别表示跷跷板左右两侧的物体体重，(d_l)、(d_r) 分别表示左右两侧物体到跷跷板中央支点的距离。

将跷跷板扩展为多层结构：(w_l) 与 (w_r) 均可以用一个子跷跷板代替。此时当且仅当当前跷跷板左右力矩相等，且所有子跷跷板都平衡时，整个跷跷板才平衡。

输入格式

采用递归方式输入数据。每行数据描述一个跷跷板，包含 4 个用空格分隔的非负整数 (w_l,d_l,w_r,d_r)。当 (w_l=0) 时，表示左侧实际上是一个子跷跷板，其描述紧接在本行之后；当 (w_r=0) 时，表示右侧实际上是一个子跷跷板。如果左右两侧都是子跷跷板，则先描述左子跷跷板，再描述右子跷跷板。因此，多层跷跷板的数据按“先左后右，深度优先”的顺序给出。

输入保证恰好描述一棵完整的多层跷跷板；实际物体重量为正整数，数字 0 仅用于表示该侧为子跷跷板。

输出格式

如果该多层跷跷板为平衡的，输出 1，否则输出 0。输出末尾换行。

样例

输入 #1

0 1 0 3
0 3 0 2
4 1 2 2
6 1 3 2
3 4 2 6

输出 #1

1

数据范围

• (0 \le w_l,d_l,w_r,d_r \le 10000)。
• 每棵输入树的节点数不超过 1000。
• 保证输入合法，且除表示子跷跷板的 0 外，实际物体重量均大于 0。