Call for Papers

题号：NC295124
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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 guaranteed 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 any available conference exists at that time, Colin will instantly submit the paper to one of the available conferences with the highest impact factor and wait for the result.
Otherwise, Colin will be pretty upset about this paper and won't submit it anymore, even if there are some further conference haven't start receiving papers.

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$ .

输入描述:

The first line contains two integers , representing the number of conferences Colin is interested in, and the number of papers Colin would like to submit.

For the following  lines, each line contains four integers , representing the information for the -th conference: it starts receiving submissions from 8 a.m. on day , the deadline is 8 p.m. on day , and authors will be notified  results at 2 p.m. on day  whether their submissions are accepted. It's guaranteed the all the  are pairwise distinct.

For the following  lines, each line contains a single integer , representing that Colin will finish the -th paper at 9 a.m. on the day .

输出描述:

For each paper, print a line with a single integer, representing the expected value of reputation points Colin could earn from it, modulo $998244353$ .

示例1

输入

复制

输出

复制

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 .

For the second paper, Colin will first submit it to the second conference with  probability of being accepted. If it is rejected, he will receive the notification on the day , then he will submit it to the fourth conference, with  probability of being accepted. If it is still rejected, he will receive the notification on day , then he will submit it to the fifth conference, with  probability of being accepted. If it is still rejected, then there is no more chance to submit it. Thus, the expected value is , which equals  modulo .