Tiến sĩ Tuấn là một nhà sinh học phân tử có rất nhiều công trình nghiên cứu về sự đa dạng của các chuỗi ADN. Chuỗi ADN là một dãy các nuclêôtít được biểu diễn bằng một xâu kí tự chỉ chứa bốn loại kí tự ~A~, ~T~, ~G~, ~X~ tương ứng với bốn loại nuclêôtít khác nhau. Ông đang nghiên cứu một chuỗi ADN được biểu diễn bởi một xâu ~N~ phần tử ~S_1 S_2 \dots S_N~. Một đoạn con ~[i, j]~ được xác định bởi vị trí phần tử bắt đầu ~i~ và vị trí phần tử kết thúc ~j~ ~(1 \le i \le j \le N)~ trong xâu là một dãy gồm các phần tử liên tiếp nhau ~S_i S_{i+1} \dots S_j~.

Tiến sĩ Tuấn định nghĩa một đoạn con là phức tạp nếu như đoạn đó chứa ít nhất hai kí tự khác nhau. Ví dụ, ~[1, 3]~ là một đoạn con phức tạp trong xâu ~ATTTG~. Tiếp theo, ông định nghĩa độ da dạng của một chuỗi ADN là số lượng đoạn con phức tạp trong xâu tương ứng. Hai đoạn con gọi là khác nhau nếu có ít nhất một trong hai vị trí bắt đầu và kết thúc của chúng là khác nhau.

Do sơ suất, tiến sĩ Tuấn làm mất thông tin một số phần tử trong chuỗi ADN đang nghiên cứu. Vì vậy, ông biểu diễn một kí tự chấm hỏi (~?~) cho mỗi phần tử bị mất thông tin.

Yêu cầu: Hãy giúp tiến sĩ Tuấn tính độ đa dạng nhỏ nhất của chuỗi ADN nêu trên khi thay mỗi kí tự chấm hỏi (~?~) bởi một trong bốn kí tự ~A~, ~T~, ~G~, ~X~.

Dữ liệu

Vào từ file văn bản ADN.INP gồm một dòng duy nhất chỉ chứa ~N~ kí tự thuộc tập ~\{A, T, G, X, ?\}~ viết liên tiếp nhau không có dấu cách ~(1 \le N \le 10^6)~.

Kết quả

Ghi ra file văn bản ADN.OUT một số nguyên là độ đa dạng nhỏ nhất tìm được.

Ràng buộc

• Có ~20\%~ số test ứng với ~20\%~ số điểm thỏa mãn: ~N \le 10~.

• ~20\%~ số test khác ứng với ~20\%~ số điểm thỏa mãn: ~N \le 20~.

• ~24\%~ số test khác ứng với ~24\%~ số điểm thỏa mãn: ~N \le 5000~.

• ~16\%~ số test khác ứng với ~16\%~ số điểm thỏa mãn: ~N \le 10^5~.

• ~20\%~ số test còn lại ứng với ~20\%~ số điểm thỏa mãn: ~N \le 10^6~.

Ví dụ

Input

A?T?G

Output

7

Giải thích

ATTTG là một chuỗi ADN có độ đa dạng ít nhất sau khi đã thay thế mỗi kí tự ~?~ bởi một trong bốn kí tự bốn kí tự ~A~, ~T~, ~G~, ~X~. Các đoạn con phức tạp bao gồm: ~[1, 2]~, ~[1, 3]~, ~[1, 4]~, ~[1, 5]~, ~[2, 5]~, ~[3, 5]~, ~[4, 5]~.

Ở một xã vùng cao có ~N~ hộ gia đình được đánh số từ ~1~ đến ~N~. Do mạnh dạn áp dụng khoa học kỹ thuật vào làm kinh tế nên trong xã có nhiều hộ gia đình đã trở nên giàu có. Trong kỳ tổng kết cuối năm vừa qua, chính quyền xã biết được hộ gia đình thứ ~i~ ~(1 \le i \le N)~ có thu nhập là ~A_i^{(0)}~. Hưởng ứng phong trào toàn dân làm kinh tế nâng cao thu nhập và thu hẹp khoảng cách giàu nghèo, bắt đầu từ năm nay, gọi là năm thứ nhất, hàng năm chính quyền xã yêu cầu với mỗi hộ gia đình, hộ thứ ~i~ ~(1 \le i \le N)~ phải nghiên cứu phương thức làm kinh tế năm trước của các hộ gia đình liên tiếp từ thứ ~L_i~ đến thứ ~R_i~ ~(1 \le L_i \le R_i \le N)~ để học hỏi kinh nghiệm.

Với mỗi hộ gia đình ~X~, nếu thu nhập năm trước lớn hơn hoặc bằng thu nhập của hộ có thu nhập cao nhất trong số các hộ gia đình mà hộ ~X~ phải học hỏi, thì hộ ~X~ giữ nguyên phương thức làm kinh tế cũ sao cho năm nay sẽ có thu nhập ổn định bằng năm trước. Trái lại, hộ ~X~ sẽ phải sửa đổi phương thức làm kinh tế với sự hỗ trợ của chính quyền sao cho thu nhập năm nay của hộ ~X~ sẽ phải bằng thu nhập cao nhất năm trước trong số các hộ mà hộ ~X~ học hỏi. Cụ thể, tại năm thứ ~t~ ~(t \ge 1)~, hộ gia đình thứ ~i~ ~(1 \le i \le N)~ sẽ có thu nhập là ~A_i^{(t)} = max(A_i^{(t - 1)}, A_{L_i}^{(t - 1)}, A_{L_{i + 1}}^{(t - 1)}, \ldots, A_{R_i}^{(t - 1)})~.

Yêu cầu: Hãy giúp chính quyền xác định bắt đầu từ năm thứ bao nhiêu thì mỗi hộ gia đình đều sẽ có thu nhập ổn định năm sau bằng năm trước.

Dữ liệu

Vào từ file văn bản INCOME.INP:

• Dòng đầu chứa một số nguyên dương ~N~ ~(N \le 3 \times 10^5)~.

• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1^{(0)}, A_2^{(0)}, \ldots, A_N^{(0)}~ ~(A_i^{(0)} \le 10^9, \forall{i} = 1, 2, \ldots, N)~.

• Dòng thứ ~i~ trong số ~N~ dòng tiếp theo chứa hai số nguyên dương ~L_i~ và ~R_i~ ~(L_i \le R_i \le N)~.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả

Ghi ra file văn bản INCOME.OUT một số nguyên ~t~ là năm mà bắt đầu từ đó trở đi, mỗi hộ gia đình đều có thu nhập ổn định năm sau bằng năm trước.

Ràng buộc

• Có ~18\%~ số test ứng với ~18\%~ số điểm thỏa mãn: ~N \le 500~.

• ~16\%~ số test khác ứng với ~16\%~ số điểm thỏa mãn: ~A_i^{(50)} = A_i^{(49)}, \forall{i} = 1, 2, \ldots, N~.

• ~20\%~ số test khác ứng với ~20\%~ số điểm thỏa mãn: ~\sum_{i=1}^n (R_i - L_i) \le 10^6~.

• ~24\%~ số test khác ứng với ~24\%~ số điểm thỏa mãn: Không tồn tại ~i, j~ ~(1 \le i, j \le N)~ thỏa mãn ~L_i \lt L_j~ và ~R_j \lt R_i~.

• ~22\%~ số test còn lại ứng với ~22\%~ số điểm không có ràng buộc gì thêm.

Ví dụ

Input

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

Output

3

Giải thích

• Ở năm đầu tiên, thu nhập các hộ lần lượt là ~(2, 3, 3, 4)~.

• Ở năm thứ hai, thu nhập các hộ lần lượt là ~(3, 3, 3, 4)~.

• Từ năm thứ ba trở đi, thu nhập của các hộ giữ nguyên là ~(3, 3, 3, 4)~.

Cuộc thi Robot tự hành năm nay có chủ đề về việc tiết kiệm năng lượng. Sân thi đấu cho các robot được thiết kế dưới dạng hình chữ nhật kích thước ~W\times L~ và được chia thành các ô vuông đơn vị, xếp thành ~W~ dòng và ~L~ cột. Ô có toạ độ ~(r,c)~ là ô nằm tại dòng thứ ~r~ từ trên xuống (~1\le r\le W~) và tại cột thứ ~c~ từ trái sang (~1\le c\le L~). Ban đầu, sân thi đấu có ~N~ trạm sạc điện cho robot, mỗi trạm đặt tại một ô khác nhau. Với mỗi lượt thi đấu, robot sẽ được đặt vào một ô bất kì, tính cả các ô đã có trạm sạc điện. Sau khi được đặt vào sân, robot sẽ phải tìm đường đi có ít bước di chuyển nhất có thể tới một trạm sạc điện. Một bước di chuyển của robot là việc di chuyển từ ô hiện tại tới một trong các ô kề cạnh nằm trong sân thi đấu, đồng thời mất đúng một đơn vị năng lượng.

Trong quá trình thi đấu, giám khảo sẽ liên tục đưa thêm vào hoặc bỏ bớt đi các trạm sạc điện trong sân. Sau mỗi lần thay đổi, đội chơi sẽ phải nạp lại mức năng lượng tối thiểu cho robot của mình để đặt lại vào một ô bất kì của sân thi đấu nhằm đảm bảo robot đến được một trạm sạc điện trước khi hết năng lượng.

Tuấn là đội trưởng đội Robot tự hành đại diện cho tỉnh mình tham gia vòng một cấp Quốc gia. Để chuẩn bị cho cuộc thi, đội Tuấn phải thiết kế và lập trình thuật toán cho robot theo luật thi đấu của ban tổ chức đề ra.

Yêu cầu: Hãy giúp Tuấn tính năng lượng tối thiểu cho robot đặt vào sân thi đấu ban đầu và năng lượng tối thiểu cho robot sau mỗi lần ban tổ chức thay đổi trạm sạc điện trong sân.

Dữ liệu

Vào từ file văn bản ROBOT.INP:

• Dòng đầu chứa bốn số nguyên dương ~W,L,N,Q~ là kích thước của sân chơi ~W\times L~, số trạm sạc điện ban đầu và số lượng truy vấn ~(W\le 15; L \le 10^9; N \le 50000; Q\le 10^5)~.

• Mỗi dòng trong số ~N~ dòng tiếp theo chứa hai số nguyên dương ~r~ và ~c~ là toạ độ của một trạm sạc điện ~(1 \le r \le W; 1 \le c \le L)~. Dữ liệu đảm bảo không có hai trạm sạc điện nào trùng toạ độ ô đặt.

• Mỗi dòng trong số ~Q~ dòng tiếp theo tương ứng với ~Q~ truy vấn thay đổi chứa hai số nguyên dương ~r~ và ~c~ ~(1 \le r \le W; 1 \le c \le L)~. Nếu ô ~(r,c)~ đang có trạm sạc điện thì ban tổ chức sẽ loại bỏ trạm đó. Trái lại, ban tổ chức sẽ bổ sung thêm vào một trạm sạc điện tại ô ~(r,c)~.

Dữ liệu đảm bảo sau mỗi truy vấn luôn có ít nhất một trạm sạc điện trên sân.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả

Ghi ra file văn bản ROBOT.OUT gồm ~Q+1~ dòng:

• Dòng đầu tiên ghi một số nguyên là năng lượng tối thiểu tìm được cho robot đặt vào sân thi đấu ban đầu.

• Dòng thứ ~i~ trong ~Q~ dòng tiếp theo ghi một số nguyên là năng lượng tối thiểu tìm được sau truy vấn thay đổi thứ ~i~.

Ràng buộc

• Có ~16\%~ số test ứng với ~16\%~ số điểm thoả mãn: ~W=1~.

• ~20\%~ số test khác ứng với ~20\%~ số điểm thoả mãn: ~W=3~.

• ~14\%~ số test khác ứng với ~14\%~ số điểm thoả mãn: ~Q,L,N\le 200~.

• ~20\%~ số test khác ứng với ~20\%~ số điểm thoả mãn: ~Q=1~.

• ~14\%~ số test khác ứng với ~14\%~ số điểm thoả mãn: ~L\le 10000~; ~Q\le 100~.

• ~16\%~ số test khác ứng với ~16\%~ số điểm không có ràng buộc gì thêm.

Ví dụ

Input

3 7 1 2
2 3
3 7
2 3

Output

5
3
8

Giải thích

Trong ví dụ trên:

• Ban đầu, năng lượng cần tìm tối thiểu là ~5~, chẳng hạn khi đặt robot vào ô ~(3, 7)~.

• Sau khi thêm trạm sạc điện ở ô ~(3, 7)~ thì năng lượng tối thiểu cần tìm là ~3~, chẳng hạn khi robot đặt vào ô ~(1, 5)~.

• Ở lần thay đổi thứ hai, do ô ~(2, 3)~ có trạm sạc điện nên trạm đó sẽ bị loại bỏ. Khi đó, năng lượng tối thiểu cần tìm là ~8~, đó là trường hợp robot đặt vào ô ~(1, 1)~.