Problem E
Mayor Election
Input: Standard Input
Output: Standard
Output
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 
posters, they will
take meters along the road.
Total
length of SAH Shoroni is 
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 democratic, 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 
and at most 
. 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 
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 
, it can be showed at
most 
times, consecutively.
No two candidates have same poster(Duh! obviously. You won’t 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 
candidate to place at
least 
posters and at most 
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 
(
), the number of test cases. This will be followed by test cases, each
preceded by a blank line. Each test case, starts with an integer 
(
), the number of mayoral candidates. This will be followed by
lines, each describing
a candidate. Each candidate description will start with three integers, 
(
) , and (
), 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 integers, 
(
) , the maximum number of times, 
poster can be placed
consecutively. After that, an integer 
(
) describes the number of queries to handle. Each of the
following lines each contain an
integer (
) , 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
Output for Sample Input
|
1 2 2 1 4 2 2 1 1 5 3 9 1 2 3 4 5 6 7 8 9 |
Case #1: |