题目描述

给一颗 $N$ 个节点的有根树，节点从 $1$ 到 $N$ 编号， $1$ 号节点为根节点，树的点和边有非负整数权值。初始时所有点点权为 $0$ ，边权输入给出。

有 $M$ 次操作，每次操作为两种操作中的一种：

第一种操作：选择一个编号为 $x$ 的节点，给定非负数值 $y$ ，节点 $x$ 数值增加 $y$ ，同时将数值 $y$ 向下扩散， $y$ 经过边权为 $z$ 的边后值会变为 $y\ and\ z$ ，其中 $and$ 为按位与运算。

这个节点的每个子节点都会得到一个被 $y$ 与其父节点连接的边的边权按位与运算后得到的值 $y'$ ，将 $y'$ 增加到对应的子节点上，以此类推向下传递，直到叶子节点。

第二种操作：询问编号为 $x$ 的节点当前的权值。

输入格式

第一行一个整数 $n$ ，表示节点数量。

接下来 $n-1$ 行，每行三个整数 $u、v、w$ ，表示 $u$ 和 $v$ 间有一条边权为 $w$ 的无向边。

接下来一行一个整数 $m$ ，表示有 $m$ 个操作。

接下来 $m$ 行，每行第一个数表示操作类型， $1$ 为 $1$ 号操作， $2$ 为 $2$ 号操作。

若为 $1$ 号操作，后面有两个数 $x$ 和 $y$ ，表示点 $x$ 增加并扩散 $y$ 的数值。

若为 $2$ 号操作，后面有一个数 $x$ ，表示询问当前点 $x$ 上的数值。

对于每个 $2$ 号操作，每次输出一行一个整数，表示询问的结果。

2
4

对于 $40\%$ 的数据： $0 < n，m \le10^{3}$ 。

对于 $100\%$ 的数据： $0 < n，m \le10^{5}$ ， $0 \le w，y \le10^{6}$ ， $1 \le u，v，x \le n$ 。