Cho ~2~ số nguyên dương ~a~ và ~b~, hãy in ra ~a \mod b~, hay ~a \% b~.

Input

• Gồm một dòng chứa hai số nguyên dương ~a,b~.

Output

• In ra ~a \% b~.

Điều kiện

• ~1 \le a \le 10^{10^5}~.
• ~1 \le b \le 10^9~.

Subtask

• ~50\%~ số điểm: ~a \le 10^9~.
• ~50\%~ số điểm: Không ràng buộc gì thêm.

Ví dụ

Input 1:

4 3

Output 1:

1

Input 2:

16 2

Output 2:

0

Cho ~3~ số nguyên tố ~a~, ~b~, ~c~ và số nguyên dương ~n~, hãy đếm xem trong khoảng từ ~1~ tới ~n~, có bao nhiêu số chia hết cho ít nhất một trong ~3~ số ~a,b,c~.

Input

• Gồm một dòng chứa ~4~ số ~a,b,c,n~, trong đó ~a,b,c~ là số nguyên tố và đôi một khác nhau, ~n~ là một số nguyên dương.

Output

• In ra số số nguyên dương trong khoảng ~[1,n]~ chia hết cho ít nhất một trong ~3~ số ~a,b,c~.

Điều kiện

• ~1 \le a,b,c \le 10^6~.
• ~1 \le n \le 10^{18}~.

Subtask

• ~50\%~ số điểm: ~n \le 10^6~.
• ~50\%~ số điểm: Không ràng buộc gì thêm.

Ví dụ

Input 1:

2 3 5 9

Output 1:

7

Input 2:

3 5 7 20

Output 2:

11

Cho mảng ~A~ gồm ~n~ số nguyên.

Bạn phải thay đổi ít nhất bao nhiêu số để mảng ~A~ chỉ gồm các số nguyên liên tiếp?

Input

• Dòng đầu tiên gồm số nguyên ~n~.
• Dòng thứ hai gồm ~n~ số nguyên ~A_i~.

Output

• In ra số lượng số nguyên ít nhất phải thay.

Điều kiện

• ~1 \le n \le 10^5~.
• ~1 \le A_i \le 10^9~.

Ví dụ

Input:

3
4 10 5

Output:

1

Chú ý: Thay ~10~ bằng ~6~.

Ràng buộc

• Subtask 1 ~(50\%)~: ~n \le 1000~.
• Subtask 2 ~(50\%)~: Không có ràng buộc gì thêm.

Vùng đất Midland đang có chiến tranh tàn khốc. Bạn đang ở vùng giao tranh, và giờ phải gửi tài liệu mật từ đơn vì tới cho sở chỉ huy. Vùng này được biểu diễn dưới dạng một ma trận ~n \times m~, ô ở hàng ~i~ cột ~j~ được gọi là ô ~(i,j)~.

Công việc này chưa bao giờ là dễ dàng. Một vài ô đã bị địch cài bom và không biết khi nào sẽ phát nổ. Bạn chỉ biết rằng loại bom này có sức công phá là ~r~, có nghĩa là nếu bom ở ô ~(i,j)~, khi nó phát nổ thì các ô ~(u,v)~ thỏa mãn ~|i-u| + |j-v| \le r~ sẽ bị tàn phá (ô ~(i,j)~ và ~(u,v)~ đều nằm trong bảng). Những ô ~(u,v)~ như vậy gọi là những ô bị ảnh hưởng bởi bom.

Đây là tài liệu mật, tất nhiên chỉ huy của bạn không muốn nhận một sự rủi ro nào, vậy nên bạn được lệnh phải tìm một đường đi ngắn nhất từ đơn vị tới sở chỉ huy sao cho không được đi qua ô nào bị ảnh hưởng bởi bom. Biết rằng bạn có thể đi sang ~4~ ô kề cạnh với ô đang đứng và mỗi ô ~(i,j)~ sẽ được miêu tả bằng một kí tự như sau:

• ~c(i,j) =~ ., nếu đây là một ô bình thường có thể đi.
• ~c(i,j) =~ *, đây là vùng nguy hiểm tuyệt đối không được đi vào.
• ~c(i,j) =~ +, đây là ô có bom, như đã nói, các ô nằm cách ô này khoảng cách không quá ~r~ (kể cả chính nó) sẽ không thể đi vào.
• ~c(i,j) =~ S, đây là đơn vị của bạn, sẽ chỉ có duy nhất một ô thế này xuất hiện.
• ~c(i,j) =~ T, đây là sở chỉ huy, sẽ chỉ có duy nhất một ô thế này xuất hiện.
  
  

Input

• Dòng đầu tiên gồm ~3~ số nguyên ~n,m,r~, miêu tả kích thước bảng và vùng ảnh hưởng của bom.
• ~n~ dòng sau, mỗi dòng gồm ~m~ kí tự miêu tả vùng đất.
• Dữ liệu luôn đảm bảo ô chứa kí tự ~S~ và ~T~ không bị ảnh hưởng bởi ô chứa bom nào.
  
  

Output

• In ra một dòng là đường đi ngắn nhất từ đơn vị tới sở chỉ huy sao cho không được đi qua ô nào bị ảnh hưởng bởi bom. Nếu không có một đường đi nào như vậy, in ra ~-1~.
  
  

Constraints

• ~1 \le n,m \le 1000~
• ~0 \le r \le 1000~
  
  

Subtasks

• ~20\%~ số điểm: Không có ô nào có ~c(i,j) = *~ hoặc ~c(i,j) = +~.
• ~20\%~ số điểm: ~r = 0~.
• ~30\%~ số điểm: ~n,m \le 100~.
• ~30\%~ số điểm: Không có ràng buộc gì thêm.
  
  

Sample Test 1

Input:

3 4 1
S...
....
...T

Output:

5

Sample Test 2

Input:

3 4 0
S.+T
*.*.
*...

Output:

7

Sample Test 3

Input:

4 4 1
S..*
*...
+.*.
.T..

Output:

8

Hè đã tới, ~mrtee~ muốn cho các học sinh của mình vận động một chút. Thầy đã lập ra một cuộc thi nhảy xa, tuy nhiên điều luật của nó thì rất lạ.

Nếu chiếu trên trục ~OX~, đường nhảy sẽ bắt đầu từ điểm ~1~ và kết thúc tại điểm ~n~. Bạn sẽ xuất phát từ điểm ~0~ và được nhảy bao nhiêu lượt tùy thích, miễn là không ra khỏi phạm vi ~[1,n]~. Tuy nhiên, mỗi lượt bạn phải nhảy một quãng đường nguyên dương và ở lần nhảy thứ ~i~, bạn phải nhảy một quãng đường có độ chia hết cho ~k+i-1~. Tất nhiên, bạn sẽ được cung cấp trước ~2~ giá trị ~n~ và ~k~.

Là một ~coder~ yêu thích toán học, bạn không quan tâm tới việc thắng thua trong cuộc thi này lắm, mà chỉ hứng thú với việc đếm xem với mỗi vị trí ~i~ thuộc đoạn ~[1,n]~, có bao nhiêu cách nhảy khác nhau từ điểm xuất phát tới đó.

Hãy thử lập trình và giải đáp câu hỏi ấy!

Input

• Gồm một dòng chứa hai số nguyên dương ~n, k~.
  
  

Output

• In ra ~n~ số nguyên, số thứ ~i~ là số cách để nhảy từ điểm ~0~ tới điểm ~i~, vì kết quả có thể rất lớn nên hãy lấy phần dư với modulo ~10^9+7~.
  
  

Constraints

• ~1 \le k \le n \le 2*10^5~
  
  

Subtasks

• ~35\%~ số điểm: ~n \le 300~.
• ~40\%~ số điểm: ~n \le 4000~.
• ~25\%~ số điểm: ~n \le 2*10^5~.
  
  

Sample Test 1

Input:

12 1

Output:

1 1 2 2 3 4 5 6 8 10 12 15

Sample Test 2

Input:

15 3

Output:

0 0 1 0 0 1 1 0 1 1 1 2 1 1 3

Giải thích

• Ở ví dụ ~1~, các cách để đến điểm ~6~ là ~[0,6],[0,4,6],[0,2,6],[0,1,3,6]~.
• Ở ví dụ ~2~, các cách để đến điểm ~15~ là ~[0,15],[0,3,12],[0,6,10,15]~

Reimu hiện đang hết tiền nên đã nhờ Marisa bắt cho ~n~ con tắc kè để đem bán, con tắc kè thứ ~i~ có màu ~A_i~. Có ~q~ ngày, mỗi ngày sẽ có một trong những sự kiện sau diễn ra:

• Con tắc kè thứ ~i~ đổi thành màu ~x~.
• Có khách đến xem các con tắc kè thứ ~l~ đến ~r~. Người khách cần biết xem có bao nhiêu màu có đúng ~k~ con tắc kè.

Vì có quá nhiều tắc kè nên Reimu nhờ các bạn đếm hộ cô nhé!

Có rất nhiều khách đến xem tắc kè nhưng đáng tiếc là khách không bao giờ mua. Reimu nghèo vẫn hoàn nghèo, ăn tắc kè thay cơm.

Input

• Dòng đầu tiên gồm ba số nguyên ~n,q,k~.
• Dòng thứ hai gồm ~n~ số nguyên ~1 \le A_i \le n~, màu của những con tắc kè.
• ~q~ dòng tiếp theo, là sự kiện của các ngày:
  • Sự kiện thứ nhất dạng 1 i x, con tắc kè thứ ~i~ đổi thành màu ~x~.
  • Sự kiện thứ hai dạng 2 l r, người khách đến xem những con tắc kè từ ~l~ đến ~r~.

Output

• Với mỗi sự kiện loại hai, bạn cần in ra số lượng màu tắc kè xuất hiện chính xác ~k~ lần.

Sample test

Input

7 6 1
1 3 2 2 2 3 3
2 1 4
2 7 7
2 7 7
1 4 2
2 2 2
1 7 1

Output

2
1
1
1

Ràng buộc

• Subtask 1 ~(30\%)~: ~1 \le n, q \le 1000~.
• Subtask 2 ~(20\%)~: ~1 \le n, q \le 10^5, A_i \le 10~.
• Subtask 3 ~(30\%)~: ~1 \le n, q \le 4 \times 10^5~, tắc kè không đổi màu.
• Subtask 4 ~(20\%)~: ~1 \le n, q \le 7 \times 10 ^4~.