Description

众所周知，小花是大自然的好朋友。

某天，小花去拜访了自己许久不见的树上朋友们。在小花眼前的是一棵点数为 $n$ 的树，树上的每个结点居住着小花的一位朋友，手里均拿着一个数字 $1$。

定义 $x\to y$ 为树上朋友 $x$ 到 $y$ 的一条路径，$s(x,y)$ 为该路径上所有树上朋友手中数字的异或和，$d(x,y)$ 表示 $x\to y$ 上的边数。每个树上朋友 $x$ 都对小花提出了一个同样的问题：

记 $u\neq x,v\neq x$ 为小花的另外两个树上朋友。若 $s(u,x)=1$ 而 $s(v,x)=0$，则 $(u,v)$ 这对朋友会在朋友 $x$ 处产生 $d(u,x)\times d(v,x)$ 的友好值。而朋友 $x$ 的幸福度为所有树上朋友在 $x$ 处产生的友好值之和。

现在，小花想知道树上所有点的幸福度在$\bmod~720021013$ 下分别是多少。你能帮帮 ta 吗？

Input Format

第 $1$ 行,一个正整数 $n$ 表示树上朋友的数目.

第 $2\sim n$ 行，每行两个整数 $u,v$ 描述树上的一条边。

Output Format

共 $n$ 行，每行一个整数。第 $i$ 行的整数表示点 $x$ 在$\bmod~720021013$ 下的幸福度。

  4
  1 2
  2 3
  3 4

  8
  4
  4
  8

 10
 1 3
 2 4
 6 8
 6 9
 3 6
 4 7
 8 10
 5 1
 9 7

 208
 378
 130
 240
 336
 90
 156
 156
 110
 272

输入数据3

见样例文件 ex.in

输出数据3

见样例文件 ex.out

Constraints

对于前 $10\%$ 的数据，$n \le 10$。

对于前 $30\%$ 的数据，$n \le 500$。

对于前 $50\%$ 的数据，$n \le 5000$。

对于另外 $10\%$ 的数据，保证树是一条链。

对于另外 $10\%$ 的数据，保证树是菊花图。

对于全部 $100\%$ 的数据，$n \le 5\times 10^5$。

Hint

如果你不明确异或和的意义：

我们称 $x,y,z$ 的异或和为 $x$ xor $y$ xor $z$。

bigskip

提示：一对合法的 $(u,v)$ ，其中 $u,v$ 二者的顺序是固定的哦。