The adjacency list of a node can be uniquely represented as disjoint intervals if we minimize the number of intervals. For example, if a node is connected to nodes 1, 2, 4, 5, 6, and 9, we can say it's connected to a minimum of three intervals [1, 2], [4, 6], and [9, 9]. Whereas [1, 2], [4, 5], [6, 6], and [9, 9] is an invalid representation because the number of intervals is not minimized.

You are given a directed graph of $n$ nodes, where the adjacency list of each node is represented using the method described above. Each interval also has one of 26 colors. Colors are represented with letters from $a$ to $z$.  

Reversing a graph means that the orientation of each directed edge in the graph is reversed; if the graph has an edge from $u$ --> $v$, the reversed graph will have the edge $v$ --> $u$.

You have to answer $q$ queries. For each query, you will be given a string of unique colors. We will consider the graph to have only the intervals of these given colors. Find the minimum number of intervals needed to represent this graph if we reverse all of its edges.

The first line of input contains two integers $n$ and $q$ ($1 \le n \le 10^5$, $1 \le q \le 500$), the number of nodes in the graph and the number of queries, respectively.

$n$ blocks of input will follow, one for each node, in the following format:

The first line of the $i^{th}$ block contains a single integer $m_i$ ($0 \le m_i$), the number of intervals adjacent to node $i$.

Each of the following $m_i$ lines contains a lowercase letter $c$ followed by two integers $l$ and $r$ ($1 \le l \le r \le n$), representing that node $i$ is connected to the interval [$l$, $r$], while $c$ is the color of the interval that will be used in the queries. The intervals are given in increasing order of $l$.

The total sum of $m_i$ doesn't exceed $2\times10^5$.

It is guaranteed that the given graph is represented in the described method.

Each of the following $q$ lines contains a string of lowercase letters, representing the colors of the intervals you need to consider in that query.

For each query, print a single line with the minimum number of intervals needed to represent the reverse of the graph if we consider it to have only the intervals with the given colors in the query.