Quỳnh vừa tham gia vòng loại ICPC tại trường của mình. Kỳ thi Quỳnh tham gia có tổng cộng ~6~ bài.

Với bài thứ ~i~ ~(1 \leq i \leq 6)~ mà Quỳnh giải được, Quỳnh nhận được ~P_i~ điểm và submit tổng cộng ~S_i~ lần. Theo luật của kỳ thi do trường của Quỳnh tổ chức. Với mỗi submit sai tức ~S_i - 1~ lần số điểm mà bài đó nhận được sẽ bị tính penalty bằng ~\frac{1}{10}~ số điểm của bài đó. Vậy nên số điểm bài thứ ~i~ của Quỳnh sẽ được tính bằng ~P_i - (S_i - 1) \times (P_i \div 10)~ (chỉ tính phần nguyên).

Nếu trong trường hợp Quỳnh submit sai quá khiến số điểm bị âm bài đó sẽ được tính là ~0~ điểm.

Quỳnh vừa đi thi về nên rất mệt, các bạn hãy giúp Quỳnh tính xem tổng số điểm mà Quỳnh nhận được sau khi tham gia kỳ thi nhé.

Input

• Gồm 6 dòng, mỗi dòng chứa 2 số nguyên ~P_i, S_i~ ~(1 \leq P_i, S_i \leq 1000)~.

Output

• Gồm 1 dòng là tổng số điểm mà Quỳnh nhận được theo yêu cầu của bài toán.

Sample

Input #1

100 1
200 2
300 1
400 3
500 4
600 2

Output #1

1790

Cho hai dãy bit ~A~, ~B~. Ta biết rằng, để thực hiện phép tính ~A + B~ cần thực hiện các phép tình từ hàng đơn vị của chúng. Ví dụ: ~A = 1011, B = 1001~ thì ~A + B = 10100~. Khi thực hiện phép cổng ở hàng đơn vị ~1 + 1 = 10~ viết ~0~ nhớ ~1~ vì đây là hệ nhị phân. Dễ thấy ~1011 + 1001~ có ~3~ phép cộng có nhớ như vậy.

Yêu cầu: Cho hai số ~A, B~. Hãy cho biết trong phép tính ~A + B~ có bao nhiêu phép tính có nhớ như vậy?

Input

• Gồm 2 dòng chứa dãy bit ~A, B~ không quá ~10^5~ ký tự, chỉ gồm các ký tự ~0~ và ~1~.

Output

• Gồm 1 dòng chứa 1 số nguyên là số phép tính có nhớ trong phép toán ~A + B~.

Sample

Input #1

1011
1001

Output #1

3

Input #2

10111
1111

Output #2

5

Sau những kỳ thi căng thẳng Quỳnh quyết định về quê để xả hơi sau những chuỗi ngày chinh chiến. Về quê cô ấy thích chơi các trò chơi với những đứa trẻ trong xóm. Trò chơi ấy như sau:

• Quỳnh có một vòng tròn gồm ~N~ ô trống.
• Có ~M~ lượt, mỗi lượt Quỳnh sẽ nhờ "lũ trẻ trong xóm" chọn giúp cô ấy 2 số ~L, R~.
• Với 2 số ~L, R~, Quỳnh sẽ thả vào mỗi ô trống 1 viên sỏi theo chiều kim đồng hồ từ ô thứ ~L~ tới ~R~.

Trò chơi kết thúc sau ~M~ lượt và có người đoán được số sỏi nhiều nhất có trong 1 hộp.

Để giành được phần quà là một chiếc kẹo nhỏ xinh do Quỳnh làm. Bạn hãy tính xem số sỏi nhiều nhất có trong 1 hộp.

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~N, M~ được phân cách nhau bởi dấu cách ~(1 \leq N, M \leq 10^6)~.
• ~M~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương ~L, R~ được phân tách nhau bởi dấu cách ~(1 \leq L, R \leq N)~.

Output

• Gồm một dòng chứa 1 số nguyên lần lượt là số sỏi nhiều nhất có trong 1 hộp sau ~M~ lượt.

Sample

Input #1

5 4
1 5
2 3
4 1
4 5

Output #1

3

Input #2

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

Output #2

4

Input #3

5 2
1 5
4 2

Output #3

2

Cho 2 số ~N, K~. Yêu cầu liệt kê tất cả các chuỗi nhị phân có độ dài ~N~ theo thứ tự từ nhỏ đến lớn, mỗi xâu ký tự gồm có đúng ~K~ bit ~1~ liên tiếp. Ví dụ: ~0110~ có 2 bit ~1~ liên tiếp, ~0101~ chỉ có 1 bit ~1~ liên tiếp.

Input

• Gồm 1 dòng chứa 2 số nguyên ~N, K~ được phân tách nhau bỏi dấu cách ~(1 \leq N \leq 20, 1 \leq K \leq N)~.

Output

• Gồm nhiều dòng, mỗi dòng chứa 1 xâu nhị phân thoả mãn điều kiện đề bài.

Sample

Input #1

5 3

Output #1

00111
01110
10111
11100
11101

Quỳnh đang nghiên cứu một số đề tài về tin học, Quỳnh nghiên cứu giá trị tuyệt đối của một dãy ~X~ đó là chênh lệch giữa phần tử lớn nhất và phần tử nhỏ nhất của dãy ~X~.

Ví dụ ta có dãy ~X = [1, 6, 9, 3, -1, 7]~, giá trị tuyệt đối của dãy ~X~ này là ~|9 - (-1)| = 10~.

Vào một ngày đẹp trời, Quỳnh mời bạn tới phòng nghiên cứu, cô ấy cho bạn một dãy ~N~ số nguyên ~A_1, A_2, \cdots , A_N~. Cô ấy nhờ bạn viết 1 chương trình máy tính thực hiện ~Q~ phép toán trên dãy trên để có thể dữ liệu về nghiên cứu của mình, ~Q~ phép toán này có 2 loại:

• ~1 \ u \ v~: Phép toán này sẽ gán giá trị ~A_u = v~ ~(1 \leq u \leq N, -10^9 \leq v \leq 10^9)~.
• ~2 \ u \ v~: Phép toán này sẽ tính giá trị tuyệt đối của dãy ~A_u, A_{u + 1}, \cdots , A_v~ ~(1 \leq u \leq v \leq N)~.

Bạn hãy giúp Quỳnh viết chương trình thực hiện ~Q~ phép toán trên.

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~N, Q~ được phân tách nhau bởi dấu cách ~(1 \leq N, Q \leq 2 \times 10^5)~.
• Dòng tiếp theo gồm ~N~ số nguyên của dãy ~A_1, A_2, \cdots , A_N~ ~(-10^9 \leq A_i \leq 10^9)~.
• ~Q~ dòng tiếp theo, mỗi dòng thể hiện 1 trong 2 phép toán nêu trên.

Output

• Gồm nhiều dòng, mỗi dòng trả lời các phép toán loại ~2 \ u \ v~.

Sample

Input #1

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

Output #1

3
4
7

Phát đang phải hoàn thành bài tập cuối kì của mình, bài toán của Phát như sau.

Cho một bánh xe của 3 số nguyên ~A, B, C~, và một số ~M~ là số nguyên tố, bánh xe có ~N~ lần xoay, trước mỗi lần xoay, Phát sẽ tính ~X~ kết quả của phép toán ~{A^B}^C~ sau đó lấy kết quả sau khi chia phần dư cho ~M~. Sau đó với mỗi lần xoay, Phát sẽ hoán đổi vị trí ~A \rightarrow B,\ B \rightarrow C,\ C \rightarrow A~, sau đó tiếp tục thực hiện các thao tác trên cho tới khi hoàn thành ~N~ lần xoay.

Bài toán kết thúc bằng ~Q~ câu trả lời, mỗi câu hỏi gồm 2 số ~L, R~ yêu cầu bạn trả lời trong phép xoay thứ ~L~ tới phép xoay thứ ~R~ tổng ~X~ của tất cả các phép xoay này là bao nhiêu ?

Input

• Dòng đầu tiên gồm 2 số ~N, M, Q~ được phân tách nhau bởi dấu cách ~(1 \leq N \leq 3 \times 10^5,\ 1 \leq M \leq 10^9,\ 1 \leq Q \leq 10^5)~.
• Dòng tiếp theo gồm 3 số nguyên ~A, B, C~ ~(1 \leq A, B, C \leq 10^9)~.
• ~Q~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên ~L, R~ ~(1 \leq L \leq R \leq N)~.

Output

• Gồm ~Q~ dòng trả lời từ phép xoay thứ ~L~ đến phép xoay thứ ~R~ tổng của các ~X~ là bao nhiêu.

Sample

Input #1

10 37 3
36 29 98
1 10
5 8
4 4

Output #1

225
64
36