Page Contents

## String Power STRPOW April Long Challenge 2021

Chef has been recently studying strings and probabilities and he came up with a problem for you.

Consider an alphabet with N characters (denoted by c1,c2,…,cN). For each valid i, the character ci has a power ai; the power of a string that contains only characters from this alphabet is the sum of their powers (if a character occurs multiple times, its power also occurs in the sum multiple times). For example, the power of a string c1c2c3 is a1+a2+a3 and the power of a string c1c2c1 is 2⋅a1+a2.

Also, for each valid i, you are given two parameters pi and Bi, where pi is a non-negative integer and Bi∈{0,1}. For an integer K, we can construct a random string S with length K in the following way:

Define R=∑i=1Npi.

First, each of the K characters of S is chosen independently. For each valid i and j, the i-th character of S is cj with probability pj/R.

Then, for each valid i, we compute the number of occurrences of ci in S and if the parity of this number of occurrences (i.e. its remainder modulo 2) is different from Bi, we discard the string S and try to construct a new random string S from the beginning.

Otherwise (if the parities of occurrences of all characters match the sequence B), we have constructed the random string S.

All parameters are chosen in such a way that there is at least one string we can generate without discarding it. In particular, R>0.

What is the expected value of the power of the constructed string S? You need to answer Q queries. In each query, you are given a different value of K and you should find the expected power.

For each query, it can be proved that the expected power can be represented as a fraction PQ, where P and Q are non-negative integers and Q is coprime with 998,244,353. You need to compute P⋅Q−1 modulo 998,244,353, where Q−1 denotes the multiplicative inverse of Q modulo 998,244,353.

Input

The first line of the input contains a single integer N.

N lines follow. For each valid i, the i-th of these lines contains three space-separated integers ai, pi and Bi.

The next line contains a single integer Q.

Q lines follow. Each of these lines contains a single integer K describing a query.

Output

For each query, print a single line containing one integer P⋅Q−1 modulo 998,244,353.

Constraints

1≤N≤2,000

1≤ai≤4⋅108 for each valid i

0≤pi≤2,000 for each valid i

1≤R≤2,000

Bi∈{0,1} for each valid i

1≤Q≤2⋅104

1≤K≤4⋅108

Subtasks

Subtask #1 (2 points, time limit 1 second): N,K≤15

Subtask #2 (8 points, time limit 1.5 seconds):

K≤2,000

Q≤104

Subtask #3 (10 points, time limit 1.5 seconds): N,R≤400

Subtask #4 (80 points, time limit 2.5 seconds): original constraints

Example Input

2

1 1 0

2 2 1

2

1

3

Example Output

2

855638022

Explanation

In the first query, we can only generate the one-character string c2. Therefore, the expected power is 2.

In the second query, we can generate the following strings:

c1c1c2 with power 4 and probability 2/14

c1c2c1 with power 4 and probability 2/14

c2c1c1 with power 4 and probability 2/14

c2c2c2 with power 6 and probability 8/14

The expected power is therefore 2⋅4+2⋅4+2⋅4+8⋅62+2+2+8=367=855,638,022.

*April Long Challenge 2021 Solutions*

*April Long Challenge 2021 Solutions*

- Chef and Dice SDICE Solution
- Worthy Matrix KAVGMAT Solution
- Binary String MEX MEXSTR Solution
- Boolean Game BOOLGAME Solution
- Tree Permutations TREEPERM Solution
- Destroy the EMP Chip CHAOSEMP Solution
- Chef and Pair Flips PAIRFLIP Solution
- String Power STRPOW Solution
- Brahma and Shiva SHRINES Solution
- Water Sort Puzzle (Challenge) WTRSORT Solution
- World Record BOLT Solution
- Strong Language SSCRIPT Solution
- Valid Pair SOCKS1 Solution

*Codechef Long Challenge Solutions*

*Codechef Long Challenge Solutions*

*February Long Challenge 2021*

*February Long Challenge 2021*

#### 1. Frog Sort Solution Codechef

#### 2. Chef and Meetings Solution Codechef

#### 3. Maximise Function Solution Codechef

#### 4. Highest Divisor Solution Codechef

#### 5. Cut the Cake Challenge Solution Codechef

#### 6. Dream and the Multiverse Solution Codechef

#### 7. Cell Shell Solution Codechef

#### 8. Multiple Games Solution Codechef

#### 9. Another Tree with Number Theory Solution Codechef

#### 10. XOR Sums Solution Codechef

#### 11. Prime Game Solution CodeChef

#### 12. Team Name Solution Codechef

### January Long Challenge 2021

**Chef and Division 3 DIVTHREE SOLUTION Code Chef****Encoded String DECODEIT SOLUTION Code Chef****Point Of Impact BILLRD SOLUTION Code Chef****Fair Elections FAIRELCT SOLUTION Code Chef****Watching CPL WIPL SOLUTION Code Chef****Chef and Ants ANTSCHEF SOLUTION Code Chef****Blackjack BLKJK SOLUTION Code Chef****And-Or Game ORAND SOLUTION Code Chef****Stack-Queue Sort (Challenge) SQSORT SOLUTION Code Chef****Expected Number of SCCs RCTEXSCC SOLUTION Code Chef****Curious Matrix CURMAT SOLUTION Code Chef****Cool Subsets COOLSBST SOLUTION Code Chef****Sequence Creation ARCRT SOLUTION Code Chef****Greedy Students GRDSTD SOLUTION Code Chef**

### November Challenge 2020 SOLUTION CodeChef

- Ada and Dishes SOLUTION ADADISH
- Iron Magnet and Wall SOLUTION FEMA2
- Magical Candy Store SOLUTION CNDYGAME
- Unusual Queries SOLUTION UNSQUERS
- Red-Black Boolean Expression SOLUTION RB2CNF
- Chef and the Combination Lock SOLUTION CHEFSSM
- Scalar Product Tree SOLUTION SCALSUM
- Connect on a Grid (Challenge) SOLUTION CONGRID

### October Lunchtime 2020 CodeChef SOLUTIONS

- AND Plus OR SOLUTION ANDOR
- Chef and Subtree MEXs SOLUTION SUBMEXS
- Chef Likes Good Sequences SOLUTION GSUB
- Cute Chef Gift SOLUTION COPAR
- Chef Is Just Throwing Random Words SOLUTION SSO
- Counting Spaghetti SOLUTION CDSUMS
- Chef and Edge Flipping SOLUTION EFLIP

*RELATED :*

- Top Best Keylogger in Python 3 Make One
*What is Hacking?**Secrets of the Deep Dark Web**CODECHEF September Lunchtime 2020 SOLUTIONS**August Lunchtime 2020 SOLUTIONS*

*Related :*

*A. Shandom Ruffle SOLUTION**B. Pear TreaP SOLUTION**C. Sneetches and Speeches 3 SOLUTION**D. The Grim Treaper SOLUTION**Y. Sneetches and Speeches 1 SOLUTION**Z. Trick or Treap SOLUTION**A. Floor Number SOLUTION CODE FORCES**B. Symmetric Matrix SOLUTION CODE FORCES**C. Increase and Copy SOLUTION CODE FORCES**D. Non-zero Segments SOLUTION CODE FORCES**E. Rock, Paper, Scissors SOLUTION CODE FORCES**F. Number of Subsequences SOLUTION CODE FORCES*

*Related :*

*Chef and Easy Queries SOLUTIONS CHEFEZQ**Covid Run SOLUTIONS CVDRUN OCTOBER CHALLENGE**Positive AND SOLUTIONS POSAND**Replace for X SOLUTIONS REPLESX**Village Road Network SOLUTIONS VILLNET**Random Knapsack SOLUTIONS RANDKNAP**D-Dimensional MST SOLUTIONS DDIMMST**Compress all Subsegments SOLUTIONS SEGCOMPR**Adding Squares SOLUTIONS ADDSQURE**Inversions SOLUTIONS INVSMOD2 OCOTBER CHALLENGE**Rooted Minimum Spanning Tree SOLUTIONS ROOTMST*