~Duck~ rất mê cái đẹp, anh ta không những mê gái mà còn mê cả xâu. Một xâu ~Duck~ cho là đẹp nếu nó tồn tại một cách sắp xếp sao cho xâu đó là một palindrome. Một hôm một người bạn của anh ta đưa cho anh một xâu ~S~, và với tính tò mò của mình, ~Duck~ đã dành hàng tiếng để đếm số xâu con ~[l, r]~ ~(1 \le l \le r \le n)~ của xâu ~S~ sao cho nó là một xâu đẹp. Nhưng vì xâu ~S~ quá dài nên ~Duck~ đang cần bạn giúp!

Một xâu palindrome được định nghĩa là xâu khi đọc từ trái sang phải và ngược lại đều có kết quả như nhau.

Input

• Dòng đầu gồm một số nguyên ~n~ là chiều dài của xâu ~S~ ~(1 \le n \le 10^5)~
• Dòng thứ hai là xâu ~S~ có chiều dài ~n~ chỉ gồm các ký tự từ ~[a, z]~ viết thường và các số thuộc ~[0, 9]~

Output

• In ra một số duy nhất là số xâu con đẹp trong xâu ~S~.

Sample Input 1

5
abacc

Sample Output 1

9

Sample Input 2

5
bedao

Sample Output 2

5

Subtask

• ~10\%~ số test thoả mãn xâu ~S~ chỉ gồm ~2~ ký tự 'a' và 'b'
• ~30\%~ số test tiếp theo có ~n \le 2 \times 10^3~
• ~60\%~ số test còn lại không có điều kiện gì thêm

Cây là một đồ thị vô hướng liên thông mà không có chu trình. Giữa hai đỉnh bất kì trên cây, có một và chỉ một đường đi đơn. Ta định nghĩa khoảng cách giữa hai đỉnh là số cạnh trên đường đi đơn duy nhất này.

Cho một cây gồm n đỉnh, các đỉnh được đánh số từ 1 đến ~n~. Cho một số nguyên ~k~, hãy đếm số cặp đỉnh (u, v) trên cây sao cho khoảng cách giữa ~u~ và ~v~ lớn hơn hoặc bằng ~k~. Hai cặp đỉnh (u, v) và (v, u) được tính là giống nhau.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ là số đỉnh của cây và số nguyên ~k~ (~1 \le k < n \le 5 \times 10^5~).
• Trong ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên u và v (~1 \le u, v \le n~) cho biết trên cây có một cạnh nối hai đỉnh u và v.

Output

• In ra một số nguyên duy nhất là số cặp đỉnh (u, v) sao cho khoảng cách từ u đến v là k.

Example

Sample Input

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

Sample Output

8

Note

• Các cặp đỉnh có khoảng cách bằng 3 là: (7, 4), (7, 1), (4, 5), (4, 6), (3, 5) và (3, 6).

Bảo Bay Bổng được mời về làm việc cho cơ quan hàng không vũ trụ NASAR. Cơ quan này đang thực hiện một dự án khám phá hành tinh XYZ, nơi được cho là xuất hiện sự sống. Vì hành tinh XYZ rất lớn nên cơ quan này mới đi thám hiểm được một phần diện tích hình chữ nhật có kích thước ~m \times n~, với các hàng được đánh số từ ~1~ tới ~m~ và các cột được đánh số từ ~1~ tới ~n~.

Những khu vực ngoài hình chữ nhật này được coi là nguy hiểm và không được phép làm việc tại đó. Trong khu vực ~m \times n~ này, người ta đã chọn ra một số vị trí có toạ độ nguyên để xây dựng ~S~ trạm phát sóng và ~T~ trạm thu sóng phục vụ cho công việc nghiên cứu (ở cùng một toạ độ có thể đặt đồng thời nhiều trạm phát sóng và thu sóng). Vào thời điểm ~0~, các trạm phát sóng sẽ đồng loạt phát ra các nguồn sóng. Nếu ở thời điểm ~t~, sóng đang ở toạ độ ~(i, j)~ thì ở thời điểm ~t + 1~, sóng sẽ lan sang ~4~ ô kề cạnh với nó, cụ thể là ~(i - 1, j)~,~(i, j - 1)~,~(i + 1, j)~,~(i, j + 1)~. Thời điểm để một trạm thu sóng nhận được sóng là thời điểm nhỏ nhất sao cho có sóng từ một trạm phát sóng nào đó lan ra tới toạ độ trạm thu sóng này.

Hiện giờ, thời gian để tất cả các trạm thu sóng đều nhận được sóng là lâu hơn so với kế hoạch của NASAR cho nên họ muốn nhờ Bảo Bay Bổng công việc như sau: Hãy tìm cách đặt thêm một trạm phát sóng nữa sao cho thời gian để toàn bộ ~T~ thiết bị thu sóng đều nhận được sóng là nhỏ nhất có thể. Đồng thời, hãy đếm xem có bao nhiêu vị trí có thể đặt trạm phát sóng mới để đạt được thời gian đó.

Bảo Bay Bổng đã giải quyết hai vấn đề trên nhưng chưa chắc chắn về kết quả của mình. Bảo Bay Bổng muốn nhờ bạn tính toán lại để đối chiếu kết quả. Hãy giúp Bảo Bay Bổng hoàn thành công việc của NASAR giao cho.

Input: Nhập từ file "THUPHATSONG.INP"

• Dòng đầu tiên chứa hai số nguyên dương ~m, n~ ~(1 \le m, n \le 10^5)~.
• Dòng thứ hai chứa hai số nguyên không âm ~S, T~ ~(0 \le S \le 10^5, 1 \le T \le 10^5)~.
• ~S~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x, y~ là toạ độ của các trạm phát sóng ~(1 \le x \le m, 1 \le y \le n)~.
• ~T~ dòng cuối cùng, mỗi dòng chứa hai số nguyên ~x, y~ là toạ độ của các trạm thu sóng ~(1 \le x \le m, 1 \le y \le n)~.

Output: Xuất ra file "THUPHATSONG.OUT"

In ra hai số nguyên cách nhau bởi một dấu cách:

• Số thứ nhất là thời gian nhỏ nhất để tất cả ~T~ trạm thu sóng nhận được sóng sau khi xây thêm trạm phát sóng thứ ~S + 1~.

• Số thứ hai là số lượng vị trí có thể đặt trạm phát sóng thứ ~S + 1~. Các vị trí này phải là các toạ độ nguyên nằm trong phạm vi hinh chữ nhật an toàn ~m \times n~ và giúp cho thời gian để toàn bộ ~T~ trạm thu sóng nhận được sóng là nhỏ nhất có thể.

Ví Dụ

Sample Input 1

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

Sample Output 1

1 4

Sample Input 2

2 3
0 1
1 1

Sample Output 2

0 1

Sample Input 3

2 3
1 1
1 2
1 2

Sample Output 3

0 6

Giải thích

• Hình ảnh minh hoạ cho ví dụ đầu tiên:

  • Các trạm thu sóng kí hiệu lần lượt là ~T_1, T_2, T_3, T_4~.

  • Trạm phát sóng thứ nhất kí hiệu là ~S_1~, phát ra sóng màu xanh lá cây.

  • Trạm phát sóng thứ hai kí hiệu là ~S_2~, phát ra sóng màu xanh da trời.

  • Trạm phát sóng được đặt thêm vào kí hiệu là ~S_3~, phát ra sóng màu vàng.

  • Dưới đây là hình ảnh của các trạm sóng khi chưa đặt thêm trạm phát sóng mới:

    

  • Khi chưa đặt thêm trạm phát sóng mới, các trạm thu sóng ~T_1, T_2, T_4~ nhận được sóng tại thời điểm ~1~. Trong khi đó, trạm ~T_3~ nhận được sóng tại thời điểm ~2~. Do đó, thời gian nhỏ nhất để tất cả các trạm đều nhận được sóng là thời điểm ~2~.

  • Dưới đây là hình ảnh của các cách đặt trạm sóng ~S_3~ để thời gian tất cả các trạm thu sóng nhận được sóng là nhỏ nhất có thể:

  

  • Bây giờ, tất cả các trạm thu sóng đều nhận được sóng tại thời điểm ~1~.

• Ở ví dụ thứ hai, việc đặt trạm phát sóng tại ~(1, 1)~ sẽ giúp cho trạm thu sóng nhận sóng ngay tại thời điểm ~0~.

• Ở ví dụ cuối cùng, bất kể đặt trạm phát sóng mới tại đâu, trạm thu sóng đều bắt được sóng ngay tại thời điểm ~0~ do đã có sẵn một trạm phát sóng đặt trùng toạ độ tại đó.

Giới hạn

• Subtask 1 (10%): ~m, n, S, T \le 50~
• Subtask 2 (20%): ~S = 0; m, n, T \le 500~
• Subtask 3 (30%): ~S = 0~
• Subtask 4 (20%): ~m, n, S, T \le 5000~
• Subtask 5 (20%): Không có ràng buộc gì thêm

Cho một cây gồm ~n~ đỉnh, các đỉnh được đánh số từ ~1~ tới ~n~. Ban đầu cây có gốc là ~1~. Với mỗi đỉnh ~i~, ta có thêm hai tham số là ~a_i~ và ~b_i~, tức đỉnh ~i~ đại diện cho đường thẳng có dạng ~a_i \times x + b_i~.

Bạn được cho ~q~ truy vấn, mỗi truy vấn có một trong hai dạng như sau:

• ~1~ ~r~: Truy vấn loại ~1~, mang ý nghĩa đổi gốc hiện tại của cây sang đỉnh ~r~.
• ~2~ ~u~ ~x~: Xét cây con hiện tại của đỉnh ~u~ (nên nhớ gốc của cây có thể thay đổi), hãy tìm đỉnh ~v~ sao cho ~a_v \times x + b_v~ đạt giá trị lớn nhất. In ra giá trị đó.

Dữ liệu đảm bảo đáp án luôn dương. Tuy nhiên, nếu tồn tại truy vấn có đáp án bé hơn ~0~, thí sinh cần in ra ~0~ cho những truy vấn đó.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,q~ ~(1 \le n \le 2 \times 10^5, 1 \le q \le 3 \times 10^5)~.
• Dòng thứ ~2~ gồm ~n~ phần tử ~a_1,a_2,...,a_n~.
• Dòng thứ ~3~ gồm ~n~ phần tử ~b_1,b_2,...,b_n~.
• ~n-1~ dòng sau, mỗi dòng gồm ~2~ phần tử ~u_i, v_i~ miêu tả cạnh thứ ~i~ của cây.
• ~q~ dòng tiếp theo, mỗi dòng có một trong hai dạng:
  • ~1~ ~r~
  • ~2~ ~u~ ~x~

Output

• In ra đáp án của các truy vấn thứ ~2~.

Subtask

• Subtask ~1~ (~20\%~ số test): ~n \le 100, q \le 100~.
• Subtask ~2~ (~20\%~ số test): Không có truy vấn loại ~1~.
• Subtask ~3~ (~30\%~ số test): ~u=1~ với mọi truy vấn loại ~2~.
• Subtask ~4~ (~30\%~ số test): Không có ràng buộc gì thêm.

Ví dụ

Sample Input 1

5 5

2 1 4 3 1
1 2 -5 1 3

1 2
1 3
3 4
2 5

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

Sample Output 1

7
5
4
10