Colin is a first-year Ph.D. student, working hard with many beautiful but unrealistic academic fantasies. He aims to design clever algorithms for essential problems and publish them in top conferences.
There are $$$n$$$ conferences Colin is interested in. The $$$i$$$-th one starts receiving submissions at 8 a.m. on the day $$$r_i$$$ , and the deadline to submit papers is 8 p.m. on the day $$$d_i$$$. After the submitted paper has been reviewed by the experts, the authors will be notified of the result at 2 p.m. on the day $$$t_i$$$. The result is either Accepted or Rejected. In addition, there is an impact factor $$$w_i$$$ for the $$$i$$$-th conference, which represents the reputation of the conference. To simplify the problem, we guarantee that the impact factors of conferences are pairwise distinct.
But recently, he sadly found that his papers were rejected again and again. By summarizing the past data, Colin raised an assumption: the probability of acceptance for a paper is equal to the number of times it has been submitted over the impact factor of the conference. Formally, if Colin submits a paper to the $$$i$$$-th conference now, and it has already been submitted for $$$k$$$ times (including this time), then the probability of acceptance this time is equal to $$$$$$ \min(1, \frac{k}{w_i}) $$$$$$ Now Colin has $$$m$$$ papers he would like to submit, and the $$$i$$$-th paper will be finished at 9 a.m. on the day $$$f_i$$$. We say a conference is available at a time if it has already started receiving papers, but its deadline hasn't passed. Once Colin finishes each paper, if there does not exist any available conference at that time, then he will think this paper is not welcome and won't submit it anymore; if there exists any available conference at that time, he will instantly submit it to one of the available conferences with the highest impact factor. Then Colin will repeat as follows:
On the day of receiving the notification of the result, if the paper is Rejected:
If the paper is Accepted, Colin will earn reputation points, which are equal to the impact factor of the conference that accepts the paper. He will not submit the paper to other conferences.
Colin would like to ask, if his assumption is valid, what is the expected value of reputation points he can earn from each paper? If a paper is not accepted in the end, then Colin will earn $$$0$$$ reputation points from it. Please find the answer modulo $$$998244353$$$.
Notice that all the times mentioned are in AOE time, and there is no need to consider any issues related to time zones.
The first line contains two integers $$$n,m~(1\le n\le 5\times 10^3,~1\le m\le 10^5)$$$, representing the number of conferences Colin is interested in, and the number of papers Colin would like to submit.
For the following $$$n$$$ lines, each line contains four integers $$$r_i, d_i, t_i,w_i~(1\le r_i \lt d_i \lt t_i\le 10^9,~1\le w_i\le 10^8)$$$, representing the information for the $$$i$$$-th conference: it starts receiving submissions from 8 a.m. on day $$$r_i$$$, the deadline is 8 p.m. on day $$$d_i$$$, and authors will be notified of the results at 2 p.m. on day $$$t_i$$$ whether their submissions are accepted. It's guaranteed that all the $$$w_i$$$ are pairwise distinct.
For the following $$$m$$$ lines, each line contains a single integer $$$f_i~(1\le f_i\le 10^9)$$$, representing that Colin will finish the $$$i$$$-th paper at 9 a.m. on the day $$$f_i$$$.
For each paper, print a line with a single integer, representing the expected value of reputation points Colin could earn from it, modulo $$$998244353$$$.
5 31 2 3 12 3 4 23 4 5 34 5 6 45 6 7 5123
1 249561091 332748120
For the first paper, Colin will submit it to the first conference, and according to the assumption, the paper will definitely be accepted. Thus, the expected value of reputation he could earn is equal to the impact factor of the first conference, which is $$$1$$$.
For the second paper, Colin will first submit it to the second conference with $$$50\%$$$ probability of being accepted. If it is rejected, he will receive the notification on the day $$$4$$$, then he will submit it to the fourth conference, with $$$\frac{2}{4}=50\%$$$ probability of being accepted. If it is still rejected, then he will receive the notification on day $$$6$$$, then he will submit it to the fifth conference, with $$$\frac{3}{5}=60\%$$$ probability of being accepted. If it is still rejected, then there is no more chance to submit it. Thus, the expected value is $$$2\times 50\%+ 4\times 50\%\times 50\%+5\times 50\%\times 50\%\times 60\%=\frac{11}{4}$$$, which equals $$$249561091$$$ modulo $$$998244353$$$.
