Telepanting solution codeforces

Telepanting solution codeforces



An ant moves on the real line with constant speed of 11 unit per second. It starts at 00 and always moves to the right (so its position increases by 11 each second).

There are nn portals, the ii-th of which is located at position xixi and teleports to position yi<xiyi<xi. Each portal can be either active or inactive. The initial state of the ii-th portal is determined by sisi: if si=0si=0 then the ii-th portal is initially inactive, if si=1si=1 then the ii-th portal is initially active. When the ant travels through a portal (i.e., when its position coincides with the position of a portal):

  • if the portal is inactive, it becomes active (in this case the path of the ant is not affected);
  • if the portal is active, it becomes inactive and the ant is instantly teleported to the position yiyi, where it keeps on moving as normal.

How long (from the instant it starts moving) does it take for the ant to reach the position xn+1xn+1? It can be shown that this happens in a finite amount of time. Since the answer may be very large, compute it modulo 998244353998244353.

Input

The first line contains the integer nn (1n21051≤n≤2⋅105) — the number of portals.

The ii-th of the next nn lines contains three integers xixiyiyi and sisi (1yi<xi1091≤yi<xi≤109si{0,1}si∈{0,1}) — the position of the ii-th portal, the position where the ant is teleported when it travels through the ii-th portal (if it is active), and the initial state of the ii-th portal.

The positions of the portals are strictly increasing, that is x1<x2<<xnx1<x2<⋯<xn. It is guaranteed that the 2n2n integers x1,x2,,xn,y1,y2,,ynx1,x2,…,xn,y1,y2,…,yn are all distinct.

Output

Output the amount of time elapsed, in seconds, from the instant the ant starts moving to the instant it reaches the position xn+1xn+1. Since the answer may be very large, output it modulo 998244353998244353.

Examples

input

Copy
4
3 2 0
6 5 1
7 4 0
8 1 1

output

Copy
23

input

Copy
1
454971987 406874902 1

output

Copy
503069073

input

Copy
5
243385510 42245605 0
644426565 574769163 0
708622105 208990040 0
786625660 616437691 0
899754846 382774619 0

output

Copy
899754847

input

Copy
5
200000000 100000000 1
600000000 400000000 0
800000000 300000000 0
900000000 700000000 1
1000000000 500000000 0

output

Copy
3511295
Note

Explanation of the first sample: The ant moves as follows (a curvy arrow denotes a teleporting, a straight arrow denotes normal movement with speed 11 and the time spent during the movement is written above the arrow).

0665381232465274265490⟶66⇝5⟶38⇝1⟶23⇝2⟶46⇝5⟶27⇝4⟶26⇝5⟶49

Notice that the total time is 6+3+2+4+2+2+4=236+3+2+4+2+2+4=23.

Explanation of the second sample: The ant moves as follows (a curvy arrow denotes a teleporting, a straight arrow denotes normal movement with speed 11 and the time spent during the movement is written above the arrow).

0454971987454971987406874902480970864549719880⟶454971987454971987⇝406874902⟶48097086454971988

Notice that the total time is 454971987+48097086=503069073454971987+48097086=503069073.

Explanation of the third sample: Since all portals are initially off, the ant will not be teleported and will go straight from 00 to xn+1=899754846+1=899754847xn+1=899754846+1=899754847.

 



Also read : What a Reversal solution codeforces

Leave a Comment