Cho xâu \(S\) độ dài \(N\) chỉ chứa các chữ cái latin in thường, các ký tự được đánh chỉ số từ \(1\). Hãy lập trình xử lý lần lượt \(Q\) truy vấn ở hai loại sau:

• Loại \(1\): Thay đổi ký tự thứ \(i\) của \(S\) thành \(c\) (không làm gì cả nếu \(S_i=c\) sẵn).
• Loại \(2\): Đếm số lượng ký tự phân biệt xuất hiện trong xâu con từ vị trí \(l\) đến vị trí \(r\) của \(S\).

Input

Dòng đầu chứa số nguyên dương \(N\) \(\left(N\leq 5\cdot 10^5\right)\).

Dòng tiếp theo chứa xâu \(S\) bao gồm \(N\) ký tự latin in thường.

Dòng tiếp theo chứa số nguyên dương \(Q\) \(\left(Q\leq 2\cdot 10^4\right)\).

\(Q\) dòng tiếp theo có dạng 1 i c hoặc 2 l r thể hiện một truy vấn ở thể loại tương ứng.

Output

Với mỗi truy vấn loại \(2\), in ra số lượng ký tự phân biệt cần tìm.

Ví dụ

Sample input

7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7

Sample output

3
1
5

Cho \(A+B+C\) lá bài, trong đó có đúng \(A\) lá bài được ghi số \(1\), có đúng \(B\) lá bài ghi số \(0\) và \(C\) lá bài ghi số \(-1\). Bạn hãy lập trình chọn ra \(K\) lá bài trong số chúng để tổng các số được ghi trên các lá bài là lớn nhất có thể.

Input

• Một dòng duy nhất chứa bốn số nguyên \(A\), \(B\), \(C\) và \(K\).
• \(0\leq A, B, C\).
• \(1\leq K\leq A+B+C\leq 2\cdot 10^9\).

Output

In ra tổng lớn nhất tìm được.

Ví dụ

Sample input 1

2 1 1 3

Sample output 1

2

Sample input 2

1 2 3 4

Sample output 2

0

Sample input 3

2000000000 0 0 2000000000

Sample output 3

2000000000

Oanh Trúc Béo muốn đi phát quà liên khối cho \(n\) học sinh khối chuyên Tin. Các học sinh này đều đứng trên trục số và được đánh số lần lượt từ \(1\) đến \(n\), học sinh thứ \(i\) đứng ở tọa độ \(p_i\). Oanh Trúc đứng ở gốc tọa độ (điểm \(0\)) và muốn tìm một trình tự phát quà để tổng độ bất mãn của \(n\) học sinh này là nhỏ nhất có thể, biết rằng Oanh Trúc cần đúng \(1\) phút để di chuyển được một đơn vị độ dài trên trục số, đồng thời, nếu học sinh nào chưa được nhận quà, thì cứ mỗi phút trôi qua, độ bất mãn của bạn ấy sẽ tăng lên \(1\) (độ bất mãn ban đầu của mỗi người đều bằng \(0\)).

Các bạn hãy lập trình tính toán giúp Oanh Trúc độ bất mãn nhỏ nhất có thể nhé!

Input

Dòng đầu chứa số nguyên dương \(n\) \((n\leq 1000)\).

Dòng tiếp theo chứa \(n\) số nguyên \(p_1\), \(p_2\),..., \(p_n\) \(\left(-5\cdot 10^5\leq p_i\leq 5\cdot 10^5\right)\).

Output

Tổng độ bất mãn nhỏ nhất có thể.

Ví dụ

Sample input

4
-2 -12 3 7

Sample output

50

Giải thích

Trình tự tối ưu của Oanh Trúc Béo là lần lượt đi qua các điểm \(-2\), \(3\), \(7\) và \(-12\).

Oanh Trúc mất \(2\) phút để đến tọa độ \(-2\) và tổng độ bất mãn trong \(2\) phút này sẽ tăng lên \(4\cdot 2=8\).

Oanh Trúc mất tiếp \(5\) phút để đến tọa độ \(3\) và tổng độ bất mãn trong \(5\) phút này sẽ tăng lên \(3\cdot 5=15\).

Oanh Trúc mất tiếp \(4\) phút để đến tọa độ \(7\) và tổng độ bất mãn trong \(4\) phút này sẽ tăng lên \(2\cdot 4=8\).

Oanh Trúc mất tiếp \(19\) phút để đến được tọa độ \(-12\) và tổng độ bất mãn trong \(19\) phút cuối này sẽ tăng lên \(19\).

Do đó tổng độ bất mãn là \(8+15+8+19=50\).

Cho dãy số nguyên \(A\) gồm \(N\) phần tử \(A_1\), \(A_2\),..., \(A_N\), ta định nghĩa độ khó chịu của một đoạn con \([L, R]\) là giá trị \(\max(A[L], A[L+1],..., A[R])-\min(A[L], A[L+1],..., A[R])\). Hãy lập trình xác định đoạn con có độ khó chịu nhỏ nhất trong số các đoạn con \([L, R]\) với \(1\leq L < R\leq N\) của dãy \(A\).

Input

Dòng đầu chứa số nguyên dương \(N\) \(\left(2\leq N\leq 10^5\right)\).

Dòng thứ hai chứa \(N\) số nguyên mô tả dãy \(A\). Các số đều có giá trị tuyệt đối không vượt quá \(10^9\).

Output

Một số nguyên là độ khó chịu nhỏ nhất tìm được.

Ví dụ

Sample input 1

2
1 3

Sample output 1

2

Sample input 2

3
1 1 1

Sample output 2

0

Sample input 3

5
1 2 1 2 1

Sample output 3

1

Giải thích

Ở ví dụ cuối cùng, đoạn con tối ưu ta có thể chọn là \([1, 5]\), giá trị lớn nhất và nhỏ nhất của đoạn con này lần lượt là \(1\) và \(2\), ta được độ khó chịu bằng \(2-1=1\).

Lớp ITK19 có \(n\) học sinh nam, mỗi học sinh nam này đều crush đúng một trong ba bạn nữ: Oanh Trúc, Hương An và Tuyết Ny. Hoàng Hải từng khai thác hết thông tin crush-ship của từng bạn nam trong \(n\) bạn này và ghi chép hết chúng vào một cuốn sổ tay. Thật không may, Hải vừa đánh mất cuốn sổ của mình và rất tiếc nuối các thông tin quý giá mà mình đã dày công sưu tầm. Anh ấy chỉ còn nhớ đúng \(m\) thông tin: mỗi thông tin có dạng S u v hoặc D u v, trong đó, S u v đồng nghĩa với việc học sinh \(u\) và học sinh \(v\) cùng crush chung một người, còn D u v thể hiện rằng \(u\) và \(v\) crush hai người khác nhau.

Hải cho bạn biết \(m\) thông tin đó và nhờ bạn lập trình tính toán giúp có bao nhiêu trạng thái crush-ship thỏa mãn các ràng buộc mà anh đã nêu ra. Hãy giúp Hải nhé!

Input

Dòng đầu chứa hai số nguyên dương \(n\) và \(m\). (\(n\leq 15\), \(m\leq 50\))

Mỗi dòng trong \(m\) dòng tiếp theo có dạng S u v hoặc D u v thể hiện một ràng buộc tương ứng.

Output

Một số nguyên duy nhất là số trạng thái crush-ship thỏa mãn.

Ví dụ

Sample input

4 2
S 1 2
D 1 3

Sample output

18

Giải thích

Có \(6\) trạng thái hợp lệ cho ba học sinh đầu (T tượng trưng cho Oanh Trúc, A tượng trưng cho Hương An và N tượng trưng cho Tuyết Ny): TTA, TTN, AAT, AAN, NNT và NNA. Ở mỗi trạng thái trong \(6\) trạng thái trên lại có \(3\) cách chọn crush cho học sinh thứ tư, vì vậy tổng số trạng thái thỏa mãn là \(6\cdot 3=18\).

Cho dãy số nguyên dương \(A\) gồm \(N\) phần tử. Một phần tử \(A_i\) được gọi là phần tử đẹp nếu nó thỏa mãn điều kiện: không tồn tại chỉ số \(j\) nào (\(1\leq j\leq N\), \(j\neq i\)) mà \(A_i\) chia hết cho \(A_j\). Bạn hãy lập trình tính số phần tử đẹp của dãy \(A\) nhé!

Input

Dòng đầu chứa số nguyên dương \(N\) \(\left(N\leq 2\cdot 10^5\right)\).

Dòng tiếp theo chứa \(N\) số nguyên dương \(A_1\), \(A_2\),..., \(A_N\) \(\left(A_i\leq 10^6\right)\). Lưu ý rằng một số phần tử trong dãy \(A\) có thể trùng nhau.

Output

Một số nguyên duy nhất là số phần tử đẹp

Ví dụ

Sample input 1

5
24 11 8 3 16

Sample output 1

3

Sample input 2

4
5 5 5 5

Sample output 2

0

Sample input 3

10
33 18 45 28 8 19 89 86 2 4

Sample output 3

5