Problem D
Bit 4 Bit

Photo by Bennett

The two robots ZF3 and XG2 are the hosts of the music show Bit 4 Bit. On the show, they play all kinds of songs, from the famous Chips Ahoy Matey to the lesser known ones, like The Funky Algorithm. Now, they only need some playlists for the next season!

ZF3 and XG2 start out with a single playlist and want to create $P$ more. The first playlist $p_0$ contains a single song that lasts $m$ minutes. To make more playlists, ZF3 and XG2 have two operations they can do:

1. Copy two existing playlists with the same number of songs and concatenate them.

2. Copy an existing playlist and replace one of the songs.

Since they usually don’t have the time to play an entire playlist, they decide to pick a sublist instead of the entire thing. Now they wonder how long time it would take to play it.

Input

The first line contains three integers $P$, $Q$ and $m$: The number of playlists to create, the number of sublists they want to check, and the length of the song in playlist $p_0$.

Then follow $P$ lines describing how the $i$th playlist was created:

• copy $p_ i$ $p_ j$ – Copy playlist $p_ i$, then copy $p_ j$ into the list afterwards

• replace $p_ i$ $L_ i$ $T_ i$ – Copy playlist $p_ i$ and replace song $L_ i$ with a song that lasts $T_ i$ minutes

Finally, $Q$ queries on $Q$ lines follow. Each line contains three integers $p_ i$, $A_ i$ and $B_ i$, which represent a query for the total play time of the playlist $p_ i$ from the song at index $A_ i$, up to and including the song at index $B_ i$.

Output

For each query, print out the time it will take to play all the songs in the sublist. Since the numbers may grow large, output the result modulo $1\, 000\, 000\, 007$.

Limits

• $1 \leq P, Q \leq 200$

• $1 \leq m \leq 83$

• For copy operations, $|p_ i| = |p_ j|$

• For replace operations, $1 \leq T_ i \leq 83$ and $0 \leq L_ i < |p_ i|$

• $0 \leq A_ i \leq B_ i < |p_ i|$

• Playlist $i$ will only copy playlists $j$ where $j < i$

10 5 3
replace 0 0 5
copy 0 1
copy 1 0
copy 3 2
replace 4 2 4
replace 5 1 2
replace 4 3 7
copy 5 6
copy 7 5
copy 9 8
6 1 3
7 1 3
8 3 3
9 3 3
10 0 15

11
13
5
7
68