Halloween has finally arrived and the ghosts on your street have decided to volunteer at your local haunted houses. Each of the ~N~ ghosts (numbered from ~1~ to ~N~) will volunteer at exactly one of the ~5~ haunted houses and perform their prepared routine. The ~i^{th}~ ghost will perform ~k_i~ unique moves in their routine, with the ~k_i~ moves each being one of ~4~ types of moves:

• spook
• hide
• creep
• float

Each move has an associated scare factor, ~s_{move}~ for ~move \in \{spook, hide, creep, float\}~.

In addition, the ghosts are separated into groups based on the sum of the digits of their number. All ghosts who have the same sum of digits are in the same group. In order to keep the group happy, at least half of the ghosts in that group must be assigned to the same haunted house.

On Halloween night, each ghost will arrive at their assigned haunted house in the order of their number. They will ask the other ghosts inside the house if any of them are currently planning on performing any of the same moves as them in their routine. To avoid their routines being too similar, all of these ghosts that are currently inside the house (but not outside) will agree to remove that move from their routine.

Once all the ghosts have arrived, the haunted house will open, and the ghosts will perform their routines. Each move a ghost performs contributes to the scariness of the haunted house. The scariness of a haunted house is the sum of the scare factors of all moves performed by any ghost inside the house.

You will be asked ~Q~ questions. For the ~i^{th}~ question, you want to determine the number of ways to assign ghosts to the ~5~ haunted houses such that each group is happy, and the sum of the scariness of the ~5~ houses is between ~a_i~ and ~b_i~ (inclusive). Since this number can be very large, please output it modulo ~998\,244\,353~. It may be helpful to know that ~998\,244\,353~ is prime and ~998\,244\,353 = 119 \times 2^{23} + 1~.

Constraints

~1 \le N \le 80~
~1 \le Q \le 200\,000~
~1 \le k_i \le 4~ for ~1 \le i \le N~
~1 \le s_{move} \le 10^9~ for ~move \in \{spook, hide, creep, float\}~
~1 \le a_i \le b_i \le 10^9~ for ~1 \le i \le Q~

Input Specification

The first line of input contains ~2~ integers, ~N, Q~.

The next ~N~ lines of input describe the moves in the ~i^{th}~ ghost's routine. Each line begins with an integer ~k_i~, the number of unique moves in the ghost's routine. The next ~k_i~ words on the line are the moves the ~i^{th}~ ghost will perform in their routine. Each word will be one of spook, hide, creep, or float. Each move will only appear once in a ghost's routine.

The next line of input contains ~4~ integers, ~s_{spook}, s_{hide}, s_{creep}, s_{float}~.

The next ~Q~ lines of input describe the questions. Each line contains ~2~ integers, ~a_i, b_i~.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output ~Q~ lines. On the ~i^{th}~ line, output the number of ways, modulo ~998\,244\,353~, to assign ghosts to the ~5~ haunted houses such that each group is happy, and the sum of the scariness of the ~5~ houses is between ~a_i~ and ~b_i~ (inclusive). Two ways are considered different if there is at least one ghost that is assigned to a different house.

Sample Input

3 1
2 spook float
3 creep spook float
2 hide creep
10 5 7 8
19 41

Sample Output

40

Sample Explanation

There are ~20~ ways to assign ghosts to houses such that the sum of the scare factors is ~19~, and ~20~ ways such that the sum is ~41~.