Mayor Election

Somewhere in this universe, there is a city named Shohor. The people of Shohor are very democratic in nature. They will be holding their mayor election in a few months. So, all the mayor candidates are starting their campaign. All the candidates wanted to use posters in their campaigns, so they requested the election commission (EC) to permit them to put posters. After a long discussion, the election commission decided that, the candidates will be permitted to put posters along the road SAH Shoroni. But, the number of posters a particular candidate can place, is limited by the commission. All the posters are of size 1meter-by-1meter. The posters have to be placed side-by-side, so, if someone puts K posters, they will take K meters along the road. Total length of SAH Shoroni is L meters. The candidates (and also the EC) want to use every inch of the road. So, the total number of posters along the road will always be the length of the road. Although, every candidate should be given permission to place same number of posters, some of them are very influential, and somehow managed to change the number of posters they can place (I said they were demo- cratic, I never mentioned whether they were corrupt or not). For each candidate, the commission has decided that, he will be given a region of length at least li and at most ui. But no matter, how long, each candidate is allowed to cover with posters, they all sum up to the length of the road. The Election Commission Office is at one end of the road. So, any position in the road can be described the it’s distance from the office. Each candidate will be given a region [ai,bi] so that, he can place his posters in between this region. For all the candidates, the regions are non-overlapping, and completely covers the road. All the candidates have a number of different posters. If people see same posters over and over, it will become boring to them, so, they decided that, for any poster pi, it can be showed at most ci times, consecutively. No two candidates have same poster (Duh! obviously. You wont expect anyone to campaign for his opponent!). The citizen of Shohor knows the length of the road. They also know, that, the EC will permit i-th candidate to place at least ai posters and at most bi posters. The assignments of the regions will be done accordingly, that means, the posters nearest to the Election Commission office, will belong to candidate 1, then next region will belong to the candidate 2, and so on. Help the citizen of Shohor find the number of different poster sequence they will see. Input First line of input will contain an integer T (T ≤ 3), the number of test cases. This will be followed by T test cases, each preceded by a blank line. Each test case, starts with an integer N (N ≤ 50), the number of mayoral candidates. This will be followed by N lines, each describing a candidate. Each candidate description will start with three integers, Pi (Pi ≤ 10), li and ui (0 ≤ li ≤ ui ≤ 2000), the number of different posters, the minimum number of posters, he will be allowed to place, and the maximum number of posters he will be allowed. This will be followed by Pi integers, cj (1 ≤ cj ≤ 10), the maximum number of times, j-th poster can be placed consecutively. After that, an integer Q

2/2 (Q ≤ 100000) describes the number of queries to handle. Each of the following Q lines each contain an integer L (1 ≤ L ≤ 100000), the length of the road. Output For each query, output the number of ways to cover the road with posters completely. The answer can be really large. So, answer all number modulo 786433, which is also a prime number. For exact formats please see the sample input output. There will be a blank line after each test case. Sample Input 1 2 21422 1153 9 1 2 3 4 5 6 7 8 9 Sample Output Case #1: Query 1: 0 Query 2: 2 Query 3: 6 Query 4: 12 Query 5: 20 Query 6: 16 Query 7: 10 Query 8: 0 Query 9: 0