Cho 2 xâu \(A\) và \(B\) chỉ chứa các kí tự in hoa trong khoảng từ A tới Z. Kí hiệu \(|A|\), \(|B|\) lần lượt là độ dài của hai xâu \(A\) và \(B\), (\(1 \le |A|,|B| \le 50000\)). Các kí tự của mỗi xâu được đánh số từ \(1\).

Gọi \(A[i..j]\) là xâu con gồm các kí tự liên tiếp của xâu \(A\) từ vị trí thứ \(i\) đến vị trí thứ \(j\) (\(1 \le i \le j \le |A|\)). Gọi \(B[p..q]\) là xâu con gồm các kí tự liên tiếp của xâu \(B\) từ vị trí thứ \(p\) đến vị trí \(q\) (\(1 \le p \le q \le |B|\)).

Hai xâu con \(A[i..j]\) và \(B[p..q]\) được gọi là tương đồng nhau nếu tập hợp các chữ cái xuất hiện trong xâu con \(A[i..j]\) bằng với tập hợp các chữ cái xuất hiện trong xâu con \(B[p..q]\).

Xét ví dụ \(A=\) AAABBC và \(B=\) AZACAB ta có:

\(A[3..5]=\) AAB và \(B[5..6]=\) AB là tương đồng nhau vì có cùng tập hợp các chữ cái xuất hiện là {A,B}.
\(A[3..6]=\) ABBC và \(B[4..6]=\) CAB là tương đồng nhau vì có cùng tập hợp các chữ cái xuất hiện là {A,B,C}.

Yêu cầu: cho xâu \(A\) và xâu \(B\), hãy xác định số bộ \((i,j,p,q)\) (\(1 \le i \le j \le |A|, 1 \le p \le q \le |B|\)) thỏa mãn \(A[i..j]\) tương đồng với \(B[p..q]\).

Input

• Dòng thứ nhất ghi xâu \(A\).
• Dòng thứ hai ghi xâu \(B\).

Output

• Một số nguyên duy nhất là số lượng bộ \((i,j,p,q)\) thỏa mãn yêu cầu.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(1 \le |A|,|B| \le 10\).
• Subtask \(2\) (\(20\%\) số điểm): \(1 \le |A|,|B| \le 100\).
• Subtask \(3\) (\(30\%\) số điểm): \(1 \le |A|,|B| \le 1000\).
• Subtask \(4\) (\(40\%\) số điểm): \(1 \le |A|,|B| \le 50000\).

Example

AAABBC
AZACAB

34

Hộp bi của Bờm có dạng hình chữ nhật kích thước \(m \times n\) được chia thành lưới ô vuông đơn vị (\(m,n \le 10^6\)). Các hàng ô của lưới được đánh số từ \(1\) tới \(m\) từ trên xuống dưới và các cột ô của lưới được đánh số từ \(1\) tới \(n\) từ trái qua phải. Ô nằm trên giao của hàng \(x\) và cột \(y\) được gọi là ô \((x,y)\). Ban đầu hộp bi chưa có viên bi nào.

Đầu tiên, Bờm thực hiện \(k\) lần bốc bi vào hộp (\(k \le 10^6\)), ở lần thứ \(i\), Bờm bốc \(a_i\) viên bi cho thêm vào ô \((x_i,y_i)\), tổng số bi Bờm bốc không vượt quá \(10^{12}\).

Bờm nhận thấy rằng nếu để các viên bi phân bố không đều trong các ô, sẽ có ô chứa quá nhiều viên bi gây khó khăn cho việc đóng hộp. Bờm bèn chế tạo một robot để di chuyển giữa các ô sao cho tất cả các ô trong hộp đều chứa số bi giống nhau. Robot của Bờm trong một giây có thể chuyển được đúng một viên bi từ một ô sang một ô khác chung đỉnh với ô đó (chú ý là không được chuyển bi ra khỏi hộp).

Yêu cầu: Tìm cách điều khiển robot để chia đều số bi trong hộp ra các ô trong thời gian ít nhất. Cho biết thời gian robot hoàn thành công việc theo phương án tìm được.

Input

• Dòng thứ nhất chứa ba số nguyên dương \(m,n,k\).
• \(k\) dòng tiếp theo, dòng thứ \(i\) cưhas ba số nguyên dương \(x_i,y_i,a_i\).

Output

• Một số nguyên duy nhất là thời gian robot hoàn thành công việc theo phương án tìm được. Trong trường hợp robot không thể chia đều số bi trong hộp ra các ô, in ra số \(-1\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(min(m,n) \le 2\).
• Subtask \(2\) (\(25\%\) số điểm): \(m,n \le 20\).
• Subtask \(3\) (\(25\%\) số điểm): \(m,n \le 2000\).
• Subtask \(4\) (\(25\%\) số điểm): không có ràng buộc gì thêm.

Example

4 3 6
2 1 1
2 2 4
2 2 4
2 3 2
3 2 9
3 3 4

17

Một đất nước có \(n\) thành phố, các thành phố được đánh số từ \(1\) tới \(n\). Có \(m\) tuyến tàu cao tốc, mỗi tuyến kết nối trược tiếp hai thành phố khác nhau theo cả hai chiều, đảm bảo từ một thành phố bất kì có thể đi đến một thành phố bất kì khác thông qua (trực tiếp hoặc gián tiếp) \(m\) tuyến tàu cao tốc đó.

Vì kinh phí bảo trì hàng năm cho hệ thống tàu cao tốc là rất lớn, tiêu tốn một lượng lớn ngân sách của nhà nước, Bộ Giao thông và Vận tải dự định sẽ loại bỏ đúng hai tuyến tàu cao tốc trong số \(m\) tuyến (việc loại bỏ nhiều hơn hai tuyến sẽ khiến người dân phàn nà). Hai thành phố \(1\) và \(2\) là hai thành phố trọng yếu của đất nước nên việc loại bỏ các tuyến tàu phải thỏa mãn điều kiện: từ thành phố \(1\) vẫn có thể đi đến được thành phố \(2\) thông qua các tuyến tàu không bị loại bỏ.

Yêu cầu: Bạn hãy giúp Bộ Giao thông và Vận tải đếm xem có bao nhiêu cách loại bỏ đúng hai tuyến tàu thỏa mãn yêu cầu. Hai cách được gọi là khác nhau nếu có một tuyến tàu bị loại bỏ trong cách này nhưng không bị loại bỏ trong cách kia.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(m\) (\(2 \le n \le 10^5, m \le 2 \times 10^5\)) lần lượt là số lượng thành phố và số lượng tuyến tàu cao tốc.
• \(m\) dòng sau, mỗi dòng chứa hai số nguyên \(u\) và \(v\) (\(u \le n, v \le n, u \neq v\)) cho biết có một tuyến tàu cao tốc hai chiều kết nối trực tiếp thành phố \(u\) và thành phố \(v\).

Output

• Một số nguyên duy nhất là số cách loại bỏ đúng hai tuyến tàu cao tốc sao cho từ thành phố \(1\) vẫn đi đến được thành phố \(2\) thông qua các tuyến tàu cao tốc không bị loại bỏ.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(m \le 500\).
• Subtask \(2\) (\(30\%\) số điểm): \(m \le 5000\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

4 4
1 3
3 4
4 1
4 2

1