Problem Statement

Snuke có một chuỗi số nguyên ~A~ có chiều dài ~N~ .

Anh ấy sẽ thực hiện ba lần cắt giảm trong ~A~ và chia nó thành 4 (không rỗng) tiếp giáp với các chuỗi con ~B, C, D~ và ~E~ . Các vị trí các nút cắt có thể được tự do chọn.

Cho ~P,Q,R,S~ là tổng của các phần tử trong ~B,C,D,E~ , tương ứng. Snuke cảm thấy hạnh phúc khi sự khác biệt tuyệt đối của tối đa và tối thiểu giữa ~P,Q,R,S~ là nhỏ nhất. Tìm sự khác biệc tuyệt đối tối đa và tối thiểu giữa ~P,Q,R,S~

Ràng buộc

• ~4 \leq N \leq 2 \times 10^5~
• ~1 \leq A_i \leq 10^9~
• Tất cả các giá trị đầu vào là số nguyên.

Input

Đầu vào tiêu chuẩn theo định dạng sau:

~N~

~A_1~ ~A_2~ ~...~ ~A_N~

Output

Tìm sự khác biệt tuyệt đối tối đa và tối thiểu giữa ~P,Q,R,S~

Sample Input 1

5
3 2 4 1 2

Sample Output 1

2

Nếu chúng chia cho ~A~ như ~B,C,D,E=(3),(2),(4),(1,2)~ , sau đó ~P=3,Q=2,R=4,S=1+2=3~ . Ở đây, giá trị tối đa và tối thiểu giữa ~P,Q,R,S~ là ~4~ và ~2~ , với sự khác biệt tuyệt đối là ~2~ . Chúng tôi không thể tạo ra sự khác biệt tuyệt đối của mức tối đa và mức tối thiểu nhỏ hơn 2 , vì vậy câu trả lời là 2.

Sample Input 2

10
10 71 84 33 6 47 23 25 52 64

Sample Output 2

36

Sample Input 3

7
1 2 3 1000000000 4 5 6

Sample Output 3

999999994

Problem Statement

On a number line, there are ~N~ fish swimming.

Fish ~i~ , which has a weight of ~W_i~ , is at the coordinate ~X_i~ at time ~0~ and moves at a speed of ~V_i~ in the positive direction.

Takahashi will choose an arbitrary real number ~t~ greater than or equal to ~0~ and do the following action at time ~t~ just once.
Action: Choose an arbitrary real number ~x~ . Catch all fish whose coordinates are between ~x~ and ~x+A~ , inclusive.

Find the maximum total weight of fish that he can catch.

Constraints

• ~1 \leq N \leq 2000~
• ~1 \leq A \leq 10^4~
• ~1 \leq W_i\leq 10^4~
• ~0 \leq X_i\leq 10^4~
• ~1 \leq V_i\leq 10^4~
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

~N~ ~A~

~W_1~ ~X_1~ ~V_1~

~W_2~ ~X_2~ ~V_2~

~\vdots~

~W_N~ ~X_N~ ~V_N~

Output

Print the answer.

Sample Input 1

3 10
100 0 100
1 10 30
10 20 10

Sample Output 1

111

At time ~0.25~ , fish ~1~ , ~2~ , and ~3~ are at the coordinates ~25~ , ~17.5~ , and ~22.5~ , respectively. Thus, the action done at this time with ~x=16~ catches all the fish.

Sample Input 2

3 10
100 100 100
1 10 30
10 20 10

Sample Output 2

100

One optimal choice is to do the action at time ~0~ with ~x=100~ .

Sample Input 3

4 10
1000 100 10
100 99 1
10 0 100
1 1 1

Sample Output 3

1110

One optimal choice is to do the action at time ~1~ with ~x=100~ .

Problem Statement

There are ~N~ cards called card ~1~ , card ~2~ , ~\ldots~ , card ~N~ . On card ~i~ ~(1\leq i\leq N)~ , an integer ~A_i~ is written.

For ~K=1, 2, \ldots, N~ , solve the following problem.

We have a bag that contains ~K~ cards: card ~1~ , card ~2~ , ~\ldots~ , card ~K~ .
Let us perform the following operation twice, and let ~x~ and ~y~ be the numbers recorded, in the recorded order.

Draw a card from the bag uniformly at random, and record the number written on that card. Then, return the card to the bag .

Print the expected value of ~\max(x,y)~ , modulo ~998244353~ (see Notes).
Here, ~\max(x,y)~ denotes the value of the greater of ~x~ and ~y~ (or ~x~ if they are equal).

Notes

It can be proved that the sought expected value is always finite and rational. Additionally, under the Constraints of this problem, when that value is represented as ~\frac{P}{Q}~ with two coprime integers ~P~ and ~Q~ , it can be proved that there is a unique integer ~R~ such that ~R \times Q \equiv P\pmod{998244353}~ and ~0 \leq R \lt 998244353~ . Print this ~R~ .

Constraints

• ~1 \leq N \leq 2\times 10^5~
• ~1 \leq A_i \leq 2\times 10^5~
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

~N~ ~A_1~ ~A_2~ ~\ldots~ ~A_N~

Output

Print ~N~ lines. The ~i~ -th line ~(1\leq i\leq N)~ should contain the answer to the problem for ~K=i~ .

Sample Input 1

3
5 7 5

Sample Output 1

5
499122183
443664163

For instance, the answer for ~K=2~ is found as follows.

The bag contains card ~1~ and card ~2~ , with ~A_1=5~ and ~A_2=7~ written on them, respectively.

• If you draw card ~1~ in the first draw and card ~1~ again in the second draw, we have ~x=y=5~ , so ~\max(x,y)=5~ .
• If you draw card ~1~ in the first draw and card ~2~ in the second draw, we have ~x=5~ and ~y=7~ , so ~\max(x,y)=7~ .
• If you draw card ~2~ in the first draw and card ~1~ in the second draw, we have ~x=7~ and ~y=5~ , so ~\max(x,y)=7~ .
• If you draw card ~2~ in the first draw and card ~2~ again in the second draw, we have ~x=y=7~ , so ~\max(x,y)=7~ .

These events happen with the same probability, so the sought expected value is ~\frac{5+7+7+7}{4}=\frac{13}{2}~ . We have ~499122183\times 2\equiv 13 \pmod{998244353}~ , so ~499122183~ should be printed.

Sample Input 2

7
22 75 26 45 72 81 47

Sample Output 2

22
249561150
110916092
873463862
279508479
360477194
529680742

Problem Statement

There is a grid with ~H~ rows from top to bottom and ~W~ columns from left to right. Let ~(i, j)~ denote the square at the ~i~ -th row from the top and ~j~ -th column from the left.
Square ~(i, j)~ is occupied by an obstacle if ~S_{i,j}=~ # , and is empty if ~S_{i,j}=~ . .

Takahashi will install some surveillance cameras in the grid.

A surveillance camera can be placed at a square without an obstacle, in one of the four directions: up, down, left, or right.
Multiple surveillance cameras may be placed at the same square.

Each surveillance camera monitors the square it is placed at, and the squares in the direction it is placed in, as far as there is no obstacle in between.

At least how many surveillance cameras are needed to monitor all squares without an obstacle?

Constraints

• ~1 \leq H,W \leq 300~
• ~S_{i,j}~ is . or # .

Input

The input is given from Standard Input in the following format:

~H~ ~W~

~S_{1,1}\ldots S_{1,W}~

~\vdots~

~S_{H,1}\ldots S_{H,W}~

Output

Print the answer.

Sample Input 1

3 3
...
.#.
...

Sample Output 1

4

For example, if we install two surveillance cameras at square ~(1, 1)~ facing right and down, and another two at square ~(3, 3)~ facing up and left, all squares without an obstacle will be monitored.

Sample Input 2

3 5
...##
.#...
...#.

Sample Output 2

5

For example, if we install two surveillance cameras at square ~(1, 1)~ facing right and down, another at square ~(3, 3)~ facing left, and another two at square ~(2, 5)~ facing left and down, all squares without an obstacle will be monitored.

Note that the camera at square ~(2, 5)~ facing left cannot monitor square ~(2, 1)~ , since there is an obstacle in between at square ~(2, 2)~ .

Sample Input 3

14 107
...........................................................................................................
...........................................................................................................
..#########..###....###########..###.......###...###########..####.......###...###########...###########...
..########..###....###########....###.....###...###########...#####......###..###########...###########....
..#######..###.....###.............###...###....###...........######.....###..###...........###............
..######..###......###..............###.###.....###...........###.###....###..###...........###............
..#####..###.......############......#####......############..###..###...###..###...........############...
..####....###......############.......###.......############..###...###..###..###...........############...
..###......###.....###................###.......###...........###....###.###..###...........###............
..##........###....###................###.......###...........###.....######..###...........###............
..#..........###...############.......###.......############..###......#####..############..############...
..............###...###########.......###........###########..###.......####...###########...###########...
...........................................................................................................
...........................................................................................................

Sample Output 3

91

Problem Statement

Bạn có một dãy số nguyên A có chiều dài là N . Tìm sự khác biệt giữa hiệu số tối đa của 2 yếu tố (với các chỉ số khách nhau ) trong ~A~ .

Ràng buộc

• ~2 \leq N \leq 100~
• ~1 \leq A_i \leq 10^9~
• Tất cả các giá trị đầu vào là số nguyên.

Input

Đầu vào tiêu chuẩn theo định dạng sau:

~N~

~A_1~ ~A_2~ ~...~ ~A_N~

Output

In ra sự khác biệt giữa hiệu số tối đa của 2 yếu tố (với các chỉ số khách nhau ) trong ~A~ .

Sample Input 1

4
1 4 6 3

Sample Output 1

5

Sự khác biệt hiệu số tối đa giữa 2 phần tử: ~A_3-A_1=6-1=5~ .

Sample Input 2

2
1000000000 1

Sample Output 2

999999999

Sample Input 3

5
1 1 1 1 1

Sample Output 3

0

Problem Statement

Takahashi is at the origin of a number line. Takahashi wants to reach the goal at coordinate ~X~ .

Also, there are ~N~ walls and ~N~ hammers on the number line.

• At coordinates ~Y_1,Y_2,\dots,Y_N~ are walls of types ~1,2,\dots,N~ , respectively.
  • Initially, Takahashi cannot get over the walls.
• At coordinates ~Z_1,Z_2,\dots,Z_N~ are hammers of types ~1,2,\dots,N~ , respectively.
  • When he arrives at a coordinate with a hammer, he obtains the hammer.
  • The hammer of type ~i~ is dedicated to destroying the wall of type ~i~ . After he obtains the hammer of type ~i~ , he can destroy the wall of type ~i~ and get over it.

Determine if he can reach the goal. If he can, find the minimum distance he travels.

Constraints

• All values in the input are integers.
• ~1 \le N \le 1500~
• ~1 \le |X|,|Y_i|,|Z_i| \le 10^9~
• The ~(2 \times N + 1)~ coordinates ~X,Y_i~ and ~Z_i~ are distinct.

Input

The input is given from Standard Input in the following format:

~N~ ~X~

~Y_1~ ~Y_2~ ~\dots~ ~Y_N~

~Z_1~ ~Z_2~ ~\dots~ ~Z_N~

Output

If Takahashi can reach the goal, print the minimum possible distance he travels as an integer.
Otherwise, print -1 .

Sample Input 1

3 10
-2 8 -5
5 -10 3

Sample Output 1

40

Takahashi can reach the goal by traveling a distance of ~40~ as follows, which is the minimum possible:

• He starts at coordinate ~0~ .
• He moves to coordinate ~3~ to obtain the hammer of type ~3~ .
• He moves to coordinate ~5~ to obtain the hammer of type ~1~ .
• He moves to coordinate ~-2~ to destroy the wall of type ~1~ .
• He moves to coordinate ~-5~ to destroy the wall of type ~3~ .
• He moves to coordinate ~-10~ to obtain the hammer of type ~2~ .
• He moves to coordinate ~8~ to destroy the wall of type ~2~ .
• He moves to coordinate ~10~ , which is the goal.

Sample Input 2

5 -1
10 -20 30 -40 50
-10 20 -30 40 -50

Sample Output 2

1

It may not be required that he obtains a hammer or destroys a wall to reach the goal.

Sample Input 3

1 100
30
60

Sample Output 3

-1

Takahashi cannot obtain the hammer of type ~1~ , and neither can he reach the goal.

Sample Input 4

4 865942261
703164879 -531670946 -874856231 -700164975
-941120316 599462305 -649785130 665402307

Sample Output 4

4078987507

Problem Statement

Find the number of sequences of integers with ~N~ terms, ~A=(a_1,a_2,\ldots,a_N)~ , that satisfy the following conditions, modulo ~998244353~ .

• ~0 \leq a_1 \leq a_2 \leq \ldots \leq a_N \leq M~ .
• For each ~i=1,2,\ldots,N-1~ , the remainder when ~a_i~ is divided by ~3~ is different from the remainder when ~a_{i+1}~ is divided by ~3~ .

Constraints

• ~2 \leq N \leq 10^7~
• ~1 \leq M \leq 10^7~
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

~N~ ~M~

Output

Print the answer.

Sample Input 1

3 4

Sample Output 1

8

Here are the eight sequences that satisfy the conditions.

• ~(0,1,2)~
• ~(0,1,3)~
• ~(0,2,3)~
• ~(0,2,4)~
• ~(1,2,3)~
• ~(1,2,4)~
• ~(1,3,4)~
• ~(2,3,4)~

Sample Input 2

276 10000000

Sample Output 2

909213205

Be sure to find the count modulo ~998244353~ .

Problem Statement

Find the number, modulo ~998244353~ , of square matrices of size ~N~ whose elements are non-negative integers, that satisfy both of the following two conditions:

• for all ~i = 1, 2, \ldots, N~ , the sum of the elements in the ~i~ -th row is ~R_i~ ;
• for all ~i = 1, 2, \ldots, N~ , the sum of the elements in the ~i~ -th column is ~C_i~ .

Note that ~R_i~ and ~C_i~ given in the input are integers between ~0~ and ~2~ (see Constraints).

Constraints

• ~1 \leq N \leq 5000~
• ~0 \leq R_i \leq 2~
• ~0 \leq C_i \leq 2~
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

~N~

~R_1~ ~R_2~ ~\ldots~ ~R_N~

~C_1~ ~C_2~ ~\ldots~ ~C_N~

Output

Print the answer.

Sample Input 1

3
1 1 1
0 1 2

Sample Output 1

3

The following ~3~ matrices satisfy the conditions:

0 1 0
0 0 1
0 0 1



0 0 1
0 1 0
0 0 1



0 0 1
0 0 1
0 1 0

Sample Input 2

3
1 1 1
2 2 2

Sample Output 2

0

Sample Input 3

18
2 0 1 2 0 1 1 2 1 1 2 0 1 2 2 1 0 0
1 1 0 1 1 1 1 1 1 1 1 1 2 1 1 0 2 2

Sample Output 3

968235177

Be sure to print the count modulo ~998244353~ .

Problem Statement

Snuke có một chuỗi số nguyên ~A~ với chiều dài ~N~ .

Anh ấy tự do chọn số nguyên ~b~ . Ở đây, anh ta sẽ cảm thấy buồn nếu ~A_i~ và ~b+i~ cách xa nhau. Cụ thể hơn, the sadness của Snuke được tính như sau:

• ~abs(A_1 - (b+1)) + abs(A_2 - (b+2)) + ... + abs(A_N - (b+N))~

Ở đây, ~abs(x)~ là một hàm trả về giá trị tuyệt đối của ~x~ .

Tìm nổi buồn tối thiểu của Snuke.

Ràng buộc

• ~1 \leq N \leq 2 \times 10^5~
• ~1 \leq A_i \leq 10^9~
• Tất cả các giá trị đầu vào là số nguyên.

Input

Đầu vào tiêu chuẩn theo định dạng sau:

~N~

~A_1~ ~A_2~ ~...~ ~A_N~

Output

In ra nỗi buồn tối thiểu của Snuke

Sample Input 1

5
2 2 3 5 5

Sample Output 1

2

Nếu chúng ta chọn ~b=0~ , thì nỗi buồn tối thiều của Snuke sẽ là ~abs(2-(0+1))+abs(2-(0+2))+abs(3-(0+3))+abs(5-(0+4))+abs(5-(0+5))=2~ . Không có bất kì sự lựa chọn ~b~ nào nhỏ hơn 2 vì vậy đáp án là 2.

Sample Input 2

9
1 2 3 4 5 6 7 8 9

Sample Output 2

0

Sample Input 3

6
6 5 4 3 2 1

Sample Output 3

18

Sample Input 4

7
1 1 1 1 2 3 4

Sample Output 4

6

Problem Statement

There are ~N~ monsters along a number line. At the coordinate ~i~ ~(1\leq i\leq N)~ is a monster with a stamina of ~A_i~ .
Additionally, at the coordinate ~i~ , there is a permanent shield of a strength ~B_i~ .
This shield persists even when the monster at the same coordinate has a health of ~0~ or below.

Takahashi, a magician, can perform the following operation any number of times.

• Choose integers ~l~ and ~r~ satisfying ~1\leq l\leq r\leq N~ .
• Then, consume ~\max(B_l, B_{l+1}, \ldots, B_r)~ MP (magic points) to decrease by ~1~ the stamina of each of the monsters at the coordinates ~l,l+1,\ldots,r~ .

When choosing ~l~ and ~r~ , it is fine if some of the monsters at the coordinates ~l,l+1,\ldots,r~ already have a stamina of ~0~ or below.
Note, however, that the shields at all those coordinates still exist.

Takahashi wants to make the stamina of every monster ~0~ or below.
Find the minimum total MP needed to achieve his objective.

Constraints

• ~1 \leq N \leq 10^5~
• ~1 \leq A_i,B_i \leq 10^9~
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

~N~ ~A_1~ ~A_2~ ~\ldots~ ~A_N~ ~B_1~ ~B_2~ ~\ldots~ ~B_N~

Output

Print the minimum total MP needed to achieve his objective.

Sample Input 1

5
4 3 5 1 2
10 40 20 60 50

Sample Output 1

210

Takahashi can achieve his objective as follows.

• Choose ~(l,r)=(1,5)~ . Consume ~\max(10,40,20,60,50)=60~ MP, and the staminas of the monsters are ~(3,2,4,0,1)~ .
• Choose ~(l,r)=(1,5)~ . Consume ~\max(10,40,20,60,50)=60~ MP, and the staminas of the monsters are ~(2,1,3,-1,0)~ .
• Choose ~(l,r)=(1,3)~ . Consume ~\max(10,40,20)=40~ MP, and the staminas of the monsters are ~(1,0,2,-1,0)~ .
• Choose ~(l,r)=(1,1)~ . Consume ~\max(10)=10~ MP, and the staminas of the monsters are ~(0,0,2,-1,0)~ .
• Choose ~(l,r)=(3,3)~ . Consume ~\max(20)=20~ MP, and the staminas of the monsters are ~(0,0,1,-1,0)~ .
• Choose ~(l,r)=(3,3)~ . Consume ~\max(20)=20~ MP, and the staminas of the monsters are ~(0,0,0,-1,0)~ .

Here, he consumes a total of ~60+60+40+10+20+20=210~ MP, which is the minimum possible.

Sample Input 2

1
1000000000
1000000000

Sample Output 2

1000000000000000000

Sample Input 3

10
522 4575 6426 9445 8772 81 3447 629 3497 7202
7775 4325 3982 4784 8417 2156 1932 5902 5728 8537

Sample Output 3

77917796

Problem Statement

For sequences ~B=(B_1,B_2,\dots,B_M)~ and ~C=(C_1,C_2,\dots,C_M)~ , each of length ~M~ , consisting of non-negative integers, let the XOR sum ~S(B,C)~ of ~B~ and ~C~ be defined as the sequence ~(B_1\oplus C_1, B_2\oplus C_2, ..., B_{M}\oplus C_{M})~ of length ~M~ consisting of non-negative integers. Here, ~\oplus~ represents bitwise XOR.
For instance, if ~B = (1, 2, 3)~ and ~C = (3, 5, 7)~ , we have ~S(B, C) = (1\oplus 3, 2\oplus 5, 3\oplus 7) = (2, 7, 4)~ .

You are given a sequence ~A = (A_1, A_2, \dots, A_N)~ of non-negative integers. Let ~A(i, j)~ denote the contiguous subsequence composed of the ~i~ -th through ~j~ -th elements of ~A~ .
You will be given ~Q~ queries explained below and asked to process all of them.

Each query gives you integers ~a~ , ~b~ , ~c~ , ~d~ , ~e~ , and ~f~ , each between ~1~ and ~N~ , inclusive. These integers satisfy ~a \leq b~ , ~c \leq d~ , ~e \leq f~ , and ~b-a=d-c~ . If ~S(A(a, b), A(c, d))~ is strictly lexicographically smaller than ~A(e, f)~ , print Yes ; otherwise, print No .

What is bitwise XOR? The exclusive logical sum ~a \oplus b~ of two integers ~a~ and ~b~ is defined as follows.

• The ~2^k~ 's place ( ~k \geq 0~ ) in the binary notation of ~a \oplus b~ is ~1~ if exactly one of the ~2^k~ 's places in the binary notation of ~a~ and ~b~ is ~1~ ; otherwise, it is ~0~ .

For example, ~3 \oplus 5 = 6~ (In binary notation: ~011 \oplus 101 = 110~ ). What is lexicographical order on sequences?

A sequence ~A = (A_1, \ldots, A_{|A|})~ is said to be strictly lexicographically smaller than a sequence ~B = (B_1, \ldots, B_{|B|})~ if and only if 1. or 2. below is satisfied.

1. ~|A|<|B|~ and ~(A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|})~ .
2. There is an integer ~1\leq i\leq \min\\{|A|,|B|\\}~ that satisfies both of the following.
   • ~(A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})~ .
   • ~A_i < B_i~ .

Constraints

• ~1 \leq N \leq 5 \times 10^5~
• ~0 \leq A_i \leq 10^{18}~
• ~1 \leq Q \leq 5 \times 10^4~
• ~1 \leq a \leq b \leq N~
• ~1 \leq c \leq d \leq N~
• ~1 \leq e \leq f \leq N~
• ~b - a = d - c~
• All values in the input are integers.

Input

The input is given from Standard Input in the following format, where ~\text{query}_i~ represents the ~i~ -th query:

~N~ ~Q~ ~A_1~ ~A_2~ ~\dots~ ~A_N~ ~\text{query}_1~ ~\text{query}_2~ ~\vdots~ ~\text{query}_Q~

The queries are in the following format:

~a~ ~b~ ~c~ ~d~ ~e~ ~f~

Output

Print ~Q~ lines. The ~i~ -th line should contain the answer to the ~i~ -th query.

Sample Input 1

4 5
1 2 3 1
1 3 2 4 1 4
1 2 2 3 3 4
1 1 2 2 3 4
1 2 2 3 3 3
1 4 1 4 1 1

Sample Output 1

No
No
Yes
No
Yes

For the first query, we have ~A(1, 3) = (1, 2, 3)~ and ~A(2, 4) = (2, 3, 1)~ , so ~S(A(1,3),A(2,4)) = (1 \oplus 2, 2 \oplus 3, 3 \oplus 1) = (3, 1, 2)~ . This is lexicographcially larger than ~A(1, 4) = (1, 2, 3, 1)~ , so the answer is No .
For the second query, we have ~S(A(1,2),A(2,3)) = (3, 1)~ and ~A(3,4) = (3, 1)~ , which are equal, so the answer is No .

Sample Input 2

10 10
725560240 9175925348 9627229768 7408031479 623321125 4845892509 8712345300 1026746010 4844359340 2169008582
5 6 5 6 2 6
5 6 1 2 1 1
3 8 3 8 1 6
5 10 1 6 1 7
3 4 1 2 5 5
7 10 4 7 2 3
3 6 1 4 7 9
4 5 3 4 8 9
2 6 1 5 5 8
4 8 1 5 1 9

Sample Output 2

Yes
Yes
Yes
Yes
No
No
No
No
No
No

Problem Statement

We have a sequence ~A~ consisting of integer pairs. Initially, ~A = ( (0, 1), (1, 0) )~ .

You may perform the following operation on ~A~ as many (possibly zero) times as you want:

• choose adjacent two integer pairs ~(a, b)~ and ~(c, d)~ , and insert ~(a + c, b + d)~ between them.

For a sequence ~T~ consisting of integer pairs, let us define ~f(T)~ as follows:

• let ~f(T) =~ (the minimum number of operations required to make every element of ~T~ contained in ~A~ ).
  • We say that "every element of ~T~ is contained in ~A~ " if, for all elements ~x~ contained in ~T~ , ~x~ is contained in (the set consisting of the elements contained in ~A~ ).
• Here, if there are no such operations, let ~f(T) = 0~ .

There is a sequence ~S = ((a_1, b_1), (a_2, b_2), \dots, (a_N, b_N))~ consisting of ~N~ integer pairs. Here, all elements of ~S~ are pairwise distinct.
There are ~\frac{N \times (N+1)}{2}~ possible consecutive subarrays ~S_{l,r}=((a_l,b_l),(a_{l+1},b_{l+1}),\dots,(a_r,b_r))~ of ~S~ . Find the sum, modulo ~998244353~ , of ~f(S_{l,r})~ over those subarrays.
Formally, find ~\displaystyle \sum^{N} _ {l=1} \sum^{N} _ {r=l} f(S_{l,r})~ , modulo ~998244353~ .

Constraints

• ~1 \le N \le 10^5~
• ~0 \le a_i,b_i \le 10^9~
• ~a_i \neq a_j~ or ~b_i \neq b_j~ , if ~i \neq j~ .

Input

The input is given from Standard Input in the following format:

~N~

~a_1~ ~b_1~

~a_2~ ~b_2~

~\dots~

~a_N~ ~b_N~

Output

Print the answer as an integer.

Sample Input 1

7
1 2
3 7
3 5
0 0
1000000000 1
0 1
6 3

Sample Output 1

3511324

• ~f(S_{1,1})=2~ .
  • We can make ~((0,1),(1,0)) \rightarrow ((0,1),(1,1),(1,0)) \rightarrow ((0,1),(1,2),(1,1),(1,0))~ .
• ~f(S_{1,2})=5~ .
• ~f(S_{1,3})=7~ .
• ~f(S_{2,2})=5~ .
• ~f(S_{2,3})=7~ .
• ~f(S_{3,3})=4~ .
• ~f(S_{5,5})=1000000000 = 10^9~ .
• ~f(S_{5,6})=1000000000 = 10^9~ .
• ~f(S_{6,6})=0~ .
  • ~(0, 1)~ is originally contained in ~A~ .
• ~f(S_{l,r})=0~ for all ~S_{l,r}~ not mentioned above.
  • We can prove that ~A~ can never contain ~(0,0)~ or ~(6,3)~ regardless of operations.

Therefore, the sum of ~f(S_{l,r})~ is ~2000000030 = 2 \times 10^9 + 30~ , whose remainder when divided by ~998244353~ is ~3511324~ .

Problem Statement

Có ~N~ hòn đảo được xếp hàng từ tây sang đông, được kết nối bởi ~N-1~ cây cầu.

Cây cầu thứ ~i~ được kết nối với hòn đảo thứ ~i~ từ phía tây và hòn đảo thứ ~(i+1)~ từ phía tây.

Một ngày, tranh chấp đã diễn ra tại một số hòn đảo, và có ~M~ yêu cầu từ các cư dân của các hòn đảo

Yêu cầu thứ ~i~ : Tranh chấp hòn đảo thứ ~a_i~ từ phía tây và hòn đảo thứ ~b_i~ từ phía tây. Hãy làm cho việc di chuyển giữa các các cây cầu là không thể.

Bạn đã quyết định loại bỏ một sô cây cầu đáp ứng tất cả ~M~ yêu cầu.

Tìm số lượng cây cầu tối thiểu phải được gỡ bỏ.

Constraints

• Tất cả các giá trị đầu vào là số nguyên
• ~2 \leq N \leq 10^5~
• ~1 \leq M \leq 10^5~
• ~1 \leq a_i < b_i \leq N~
• Tất cả các cặp ~(a_i, b_i)~ là riêng biệt.

Input

Đầu vào tiêu chuẩn theo định dạng sau:

~N~ ~M~

~a_1~ ~b_1~

~a_2~ ~b_2~

~:~

~a_M~ ~b_M~

Output

In ra số lượng cây cầu tối thiểu cần gỡ bỏ.

Sample Input 1

5 2
1 4
2 5

Sample Output 1

1

Các yêu cầu có thể được đáp ứng bằng cách loại bỏ cây cầu nối các đảo thứ hai và thứ ba từ phía tây.

Sample Input 2

9 5
1 8
2 7
3 5
4 6
7 9

Sample Output 2

2

Sample Input 3

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

Sample Output 3

4