B. Angel Beats
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Angels are surprisingly violent, and love beating up one another! This has lead to lots of conflict in the angel world that you have decided to fix.

In an effort to establish peace, you have successfully created an alliance between $$$n$$$ groups of angels. But many other angel groups envy your alliance. To protect the alliance, you need to assemble a defense force each time an enemy angel attacks.

To do this, each group sends one of its angels to help defend. Every angel has a combat power $$$p$$$, and the combat power of the defense is the sum of combat powers of the $$$n$$$ angels sent by the groups. However, angel combat is complicated, and it requires perfect technique. In order to successfully defend against an attack of power $$$t$$$, the lowest $$$m$$$ bits of the defense's combat power must match the lowest $$$m$$$ bits of $$$t$$$. (Note that the defense's power need not be larger than that of the attacker's power.)

As the leader of the angels, you must figure out how to successfully defend against all attacks, even as angels join and leave the various groups. Hurry, you don't have much time left before the first attack!

Input

The first line contains two integers $$$n, m$$$ ($$$1 \leq n \leq 100, 1 \leq m \leq 16$$$). $$$n$$$ denotes the number of groups, and $$$m$$$ represents the number of bits used to determine which group wins.

The next $$$n$$$ lines begin with an integer $$$k$$$ ($$$1 \leq k \leq 10^3$$$), denoting the initial size of the group. Then, $$$k$$$ integers follow on that line, denoting the combat powers of the angels in the group. Combat powers are positive integers that do not exceed $$$2^m$$$.

Next, there is a line containing a single integer $$$q$$$ ($$$1 \leq q \leq 100$$$), representing the number of events that follow.

The last $$$q$$$ lines each represent an event. Each event has one of the following formats:

  • $$$+$$$ $$$i$$$ $$$p$$$: Add an angel with combat power $$$p$$$ ($$$1 \leq p \leq 2^m$$$) to group $$$i$$$ ($$$1 \leq i \leq n$$$). A group can have multiple angels of the same power level.
  • $$$-$$$ $$$i$$$ $$$p$$$: Remove an angel with combat power $$$p$$$ ($$$1 \leq p \leq 2^m$$$) from group $$$i$$$ ($$$1 \leq i \leq n$$$). Such an angel is guaranteed to exist in the group, and the group may be empty after this operation. The defense force automatically loses against any attack if a group is empty and cannot contribute an angel to the defense.
  • $$$?$$$ $$$t$$$: Compute the number of ways to select an angel from each group to successfully defend against an attack with power $$$t$$$ ($$$1 \leq t \leq 2^m$$$).
Output

For each attack, output the number of ways to successfully defend against it, mod $$$998244353$$$. There will always be at least one attack.

Example
Input
4 3
4 1 2 3 4
1 5
3 2 2 3
2 6 7
10
? 1
? 3
? 6
- 3 2
? 1
+ 2 4
? 1
- 2 4
- 2 5
? 2
Output
6
1
2
4
7
0
Note

For each of the attacks, the following sets of angels would work. Note that some are listed multiple times, since there are multiple angels with the same power level.

  • $$$\{2,5,3,7\}$$$, $$$\{3,5,2,7\}$$$, $$$\{3,5,2,7\}$$$, $$$\{3,5,3,6\}$$$, $$$\{4,5,2,6\}$$$, $$$\{4,5,2,6\}$$$
  • $$$\{4,5,3,7\}$$$
  • $$$\{1,5,2,6\}$$$, $$$\{1,5,2,6\}$$$
  • $$$\{2,5,3,7\}$$$, $$$\{3,5,2,7\}$$$, $$$\{3,5,3,6\}$$$, $$$\{4,5,2,6\}$$$
  • $$$\{2,5,3,7\}$$$, $$$\{3,4,3,7\}$$$, $$$\{3,5,2,7\}$$$, $$$\{3,5,3,6\}$$$, $$$\{4,4,2,7\}$$$, $$$\{4,4,3,6\}$$$, $$$\{4,5,2,6\}$$$
  • Since group 2 is empty, they cannot send an angel so the defense force cannot be formed.