Super Tree Energy

This problem is adapted from BalkanOI 2023 Day2 T1 "Super Tree".

You are given a rooted tree with n nodes numbered from 0 to n-1, where node 0 is the root. Each node i is assigned an integer value \(a_i\). For each node v let

[ f_v = a_v \mathbin{&} a_{p(v)} \mathbin{&} \cdots \mathbin{&} a_0, ]

where (p(v)) is the parent of (v), and the operator (&) denotes the bitwise AND operation. (For the root, (f_0 = a_0)).

The energy of the tree is defined as

[ E = \sum_{u=0}^{n-1}\sum_{v=0}^{n-1} f_u \cdot f_v = \Bigl(\sum_{v=0}^{n-1} f_v\Bigr)^2, ]

and the super energy is defined as

[ E^* = \sum_{0 \le u < v < n} f_u \cdot f_v = \frac{\left(\sum_{v=0}^{n-1} f_v\right)^2 - \sum_{v=0}^{n-1} f_v^2}{2}. ]

</p>

You will be given q update queries. In each update, you are given two integers v and x. For every node \(u\) in the subtree of \(v\) (including \(v\) itself), update \(a_u\) as follows:

[ a_u := a_u \mathbin{&} x. ]

After each update, recompute the values \(f_v\) for all nodes (note that for a node \(u\), only the values of the nodes on the simple path from \(u\) to the root affect \(f_u\)). Then, output the energy \(E\) and the super energy \(E^*\) of the tree modulo \(10^9+7\).

Note: A node \(u\) is considered to be in the subtree of node \(v\) if and only if \(v\) appears on the simple path from \(u\) to the root. In particular, the subtree of a node includes the node itself.

inputFormat

The input begins with two integers n and q (number of nodes and number of queries).

The second line contains n integers: a_0, a_1, ..., a_{n-1} representing the initial values of the nodes.

The third line contains n-1 integers. For each i from 1 to n-1, the i-th integer is the parent of node i (that is, an integer between 0 and n-1). It is guaranteed that the tree is rooted at node 0.

Each of the next q lines contains two integers v and x, representing an update query.

outputFormat

After each update query, output a line containing two integers: the current energy \(E\) and the super energy \(E^*\) of the tree, both taken modulo \(10^9+7\).

sample

5 3
7 3 6 5 4
0 0 1 1
1 6
0 3
3 2

225 68
49 16
49 16

</p>