题目描述

很久很久以前，这片大陆上充满着各式各样的国家，那时，大陆上欣欣向荣，生机勃勃。

那个时候的 $\text{Ender}$，还只是一个小孩，外出打仗的时候只会跟在大军之后，作战练习的时候也只知道和同学们相互打闹，划水。

隐隐约约的记得，那个时候，大陆上好像有个常数国吧......

在他们的带领下，这片祥和的大陆似乎始终和平发展着。可是好景不长，强大的敌人攻破了这片祥和安宁的大陆，一时间火光升天，生灵涂炭，无助的呼唤，死亡线上的徘徊，触目惊心。

多年后，$\text{Ender}$ 逐渐长大，望着死气沉沉的大陆，无语凝噎。长剑出鞘，剑指东南——重生!

勇敢的旅行者啊，愿风神护佑你。

大陆上一共有 $n$ 个重要国家，这 $n$ 个国家形成一个树形结构，标号从 $1$ 到 $n$。

每一个国家都曾繁荣过，每一个国家 $i$ 都有一个繁荣值 $a_i$。

每一个国家都曾毁灭过，每一个国家 $i$ 都有一个毁灭值 $c_i$。

风神现在把你放置在 $1$ 号国家，曾经的常数国。然后她会封锁一个国家 $p$，让你不能进入国家 $p$。你的初始兵力为 $x$，你可以选择一个你可以到达的城市 $u$，占领这个城市对你的收益是：这个城市的毁灭值 $c_u$ $\text{and}$ 你的兵力 $x$。其中，$\text{and}$ 表示按位与。

同时， 风神还会给你一个区间 $[l, r]$, 让你找寻一个标号处于 $[l, r]$ 区间中的国家 $v$ 来进行祭祀。其祭祀值是：它的繁荣值 $a_v$ $\text{and}$ 城市 $p$ 的毁灭值 $c_p$。其中，$\text{and}$ 表示按位与。

现在风神让你求出最大的，收益与祭祀值之和。

风神是聪明的， 但是 $\text{Ender}$ 也不是愚笨的。

现在风神对你挑战了 $Q$ 次，只有完成了它的挑战，$\text{Ender}$ 才能获得风神的庇护。

输入格式

第一行两个整数 $n$, $q$ 表示城市个数和挑战次数。 第 $2-n$ 行，每行两个整数 $x$, $y$, 表示树上有一条边连接这两个点。 下接 $1$ 行 $n$ 个整数，第 $i$ 个整数表示 $a_i$。 下接 $1$ 行 $n$ 个整数，第 $i$ 个整数表示 $c_i$。 下接 $q$ 行， 每行四个整数 $l, r, x, p$，表示一次挑战。

输出格式

输出共 $q$ 行，第 $i$ 行包括一个整数，表示一次挑战的答案。

5 5
1 2
2 3
2 4
2 5
2 1 3 2 3
4 5 3 0 5
2 3 0 5
2 4 2 1
1 3 0 1
3 3 0 5
2 3 4 2

1
0
0
1
5

数据规模与约定

令 $M= \max\{\max\{a\},\max\{c\}\}$。