全民制作幼儿园的蔡徐坤专属篮球场上总共有 N 个蔡徐坤专属篮球，而其中有 M 个是没气的。鉴于蔡徐坤的高超技术，他投没气的球一定能进，而投有气的球一定不能。

蔡徐坤举办了 S 场巡回篮球表演，第 i 场表演 ikun 们会指定投球个数 ki​ ，ikun 们会从 N 个蔡徐坤专属篮球中准备 ni​ 个球放在场地上，其中恰好有 mi​ 个是没气的。蔡徐坤会在这 ni​ 个蔡徐坤专属篮球中随机选出 ki​ 个投篮。如果投进了 x 个，则这次表演的失败度为 xL。ikun 们想知道这 S 场表演的期望失败度对 998244353 取模的结果。篮球表演之间相互独立。

第一行，四个正整数，N,M,S,L，表示蔡徐坤专属篮球总个数，没气的篮球总个数，蔡徐坤巡回篮球表演场数，以及失败度参数。

接下来的第 i+1 行，每行三个正整数 ni​,mi​,ki​，表示第 i 场表演蔡徐坤专属篮球个数、没气的篮球个数和 ikun 们指定的投球个数。

输出共 S 行，第 i 行为一个正整数，表示第 i 场表演的期望失败度对 998244353 取模的结果。

对于样例，我们作出如下解释：设失败度为 X，蔡徐坤有 31​ 的概率投进 2 个，有 32​ 的概率投进 1 个，期望失败度为 E(x)=323​+313∗2​=310​，310​≡332748121(mod998244353)。

子任务 1 (15%)：1≤L≤2。

子任务 2 (10%)：1≤N≤105。

子任务 3 (75%)：无特殊限制。

对于全部数据，1≤S≤200，1≤L≤2×105，1≤M≤N≤2×107。并且对于 1≤i≤S，有 1≤mi​,ki​≤ni​≤N，1≤mi​≤M。