Taylor loves trees, and this new challenge has him stumped!

Consider a tree, t, consisting of n nodes. Each node is numbered from 1 to n, and each node i has an integer, c_i, attached to it.

A query on tree t takes the form w x y z. To process a query, you must print the count of ordered pairs of integers (i, j) such that the following four conditions are all satisfied:

• i ≠ j
• i ∈ the path from node w to node x.
• j ∈ path from node y to node z.
• c_i = c_j

Given t and q queries, process each query in order, printing the pair count for each query on a new line.

Input Format

The first line contains two space-separated integers describing the respective values of n (the number of nodes) and q (the number of queries).

The second line contains n space-separated integers describing the respective values of each node (i.e., c₁, c₂, ..., c_n).

Each of the n - 1 subsequent lines contains two space-separated integers, u and v, defining a bidirectional edge between nodes u and v.

Each of the q subsequent lines contains a w x y z query, defined above.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ q ≤ 50000
• 1 ≤ c_i ≤ 10⁹
• 1 ≤ u, v, w, x, y, z ≤ n

Scoring for this problem is Binary, that means you have to pass all the test cases to get a positive score.

Output Format

For each query, print the count of ordered pairs of integers satisfying the four given conditions on a new line.

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'solve' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts following parameters:
#  1. INTEGER_ARRAY c
#  2. 2D_INTEGER_ARRAY tree
#  3. 2D_INTEGER_ARRAY queries
#

def solve(c, tree, queries):|

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

    n = int(first_multiple_input[0])

    q = int(first_multiple_input[1])