You are given a rooted tree that contains \(N\) nodes. Each node contains a lowercase alphabet.

You are required to answer \(Q\) queries of type \(u, c\), where \(u\) is an integer and \(c\) is a lowercase alphabet. The count of nodes in the subtree of the node \(u\) containing \(c\) is considered as the answer of all the queries. 

Input format

• First line: Two space-separated integers \(N\ and\ Q\) respectively
• Second line: A string \(s\) of length \(N\) (where the \(i^{th}\) character of \(s\) represents the character stored in node \(i\))
• Next \(N - 1\) line: Two space-separated integers \(u\) and \(v\) denoting an edge between node \(u\) and node \(v\)
• Next \(Q\) lines: An integer \(u\) and a space-separated character \(c\) 

Output format
For each query, print the output in a new line. 

Constraints

\(1 \leq N, Q \leq 10^5\\ 1 \leq u, v \leq N \)

• \(c\) is a lowercase alphabet
• \(s_i\) is a lowercase alphabet for all \(1 \leq i \leq N\)
• \(1\) is the root node

Note: It is guaranteed that the input generates a valid tree.