There are NN blanks arranged in a row. The blanks are numbered 1,2,…,N1,2,…,N from left to right. Tom is filling each blank with one number in {0,1,2,3}{0,1,2,3}. According to his thought, the following MMconditions must all be satisfied. The ithith condition is: There are exactly xixi different numbers among blanks ∈[li,ri]∈[li,ri]. In how many ways can the blanks be filled to satisfy all the conditions? Find the answer modulo 998244353998244353.
Input
This problem contains multiple test cases. For each test case, the first line contains an integer nn (1≤n≤105,∑n≤2×1061≤n≤105,∑n≤2×106), the number of cars. The next three lines each contains n+1n+1 integers, li,si,vili,si,vi (1≤si,vi,li≤1091≤si,vi,li≤109). It's guaranteed that si≥si+1+li+1,∀i∈[0,n−1]
Output
For each test case, output one line containing the answer. Your answer will be accepted if its absolute or relative error does not exceed 10−610−6. Formally, let your answer be aa, and the jury's answer is bb. Your answer is considered correct if |a−b|max(1,|b|)≤10−6|a−b|max(1,|b|)≤10−6. The answer is guaranteed to exist.