Sau quyết định sáp nhập tỉnh thành của Nhà nước, hai tỉnh Long An và Tây Ninh giờ đây đã trở thành anh em một nhà. Hai tỉnh Long An và Tây Ninh, mỗi tỉnh có $n$ địa điểm vui chơi giải trí được đánh số từ $1$ đến $n$, và hai điểm vui chơi có cùng số thì sẽ được xây dựng giống nhau ở hai tỉnh. Ngoài ra, mỗi tỉnh còn có $n - 1$ đường nối giữa các điểm vui chơi sao cho từ một điểm vui chơi bất kỳ có thể đi đến mọi điểm vui chơi khác. Mỗi đường nối dều có một độ dài, do đó Gấu định nghĩa khoảng cách giữa các cặp điểm như sau:

• Khoảng cách từ $u$ đến $u$ bằng $0$.
• Khoảng cách từ $u$ đến $v$ bằng $w$ với $w$ là độ dài đường nối lớn nhất trong đường đi đơn từ $u$ đến $v$.

Gấu và Mimi là hai người bạn thân qua mạng, do đó để giới thiệu tỉnh mình cho Mimi, Gấu quyết định sẽ dẫn Mimi đi chơi ở những nơi Mimi chưa từng đi. Cụ thể cuộc đi chơi sẽ diễn ra trong $m$ ngày, Gấu sẽ dẫn Mimi đi chơi ở ngày $i$ như sau:

• Vào sáng ngày $i$, Mimi sẽ tự mình đi chơi hết tất cả những địa điểm vui chơi có khoảng cách tới ~v_i~ không quá ~k_i~ ở tỉnh Tây Ninh.
• Vào trưa ngày $i$, Mimi sẽ từ Tây Ninh chạy xuống Long An và gặp mặt Gấu tại điểm $u_i$.
• Vào chiều ngày $i$, Gấu sẽ dẫn Mimi đi tất cả những địa điểm vui chơi có khoảng cách tới ~u_i~ không quá ~d_i~ ở tỉnh Long An, với điều kiện các địa điểm này Mimi chưa chơi ở Tây Ninh.
• Vào tối ngày $i$, Mimi sẽ chạy từ Long An về Tây Ninh.

Yêu cầu: Vào ngày $i$, hãy cho biết số địa điểm nhiều nhất Gấu dẫn Mimi đi chơi.

Dữ liệu vào

• Dòng đầu tiên hai chứa số nguyên $n$, $m$ $(1 \leq n, m \leq 2*10^5)$.
• $n - 1$ dòng sau, mỗi dòng chứa ba số nguyên $u, v, w$ mô tả đường nối của tỉnh Long An $(1 \leq u \neq v \leq n, 1 \leq w \leq 10^9)$.
• $n - 1$ dòng sau, mỗi dòng chứa ba số nguyên $u, v, w$ mô tả đường nối của tỉnh Tây Ninh $(1 \leq u \neq v \leq n, 1 \leq w \leq 10^9)$.
• $m$ dòng sau, mỗi dòng chứa bốn số nguyên ~u_i, v_i, d_i, k_i~ mô tả cuộc vui chơi ngày ~i~ ~(1 \leq u_i, v_i \leq n, 0 \leq d_i, k_i \leq 10^9)~.

Dữ liệu ra

Gồm một dòng chứa $m$ số là đáp án của $m$ ngày.

Ví dụ

Input

7 5
1 2 2 
1 4 7
4 5 3
4 6 9
6 7 8
2 3 5
1 2 2 
1 4 2
4 5 2
4 6 6
2 3 7
3 7 1
1 1 5 3
2 3 7 2
4 1 5 1
7 2 7 2
2 7 0 9

Output

1 4 2 1 0

Giải thích

• Vào ngày $1$, do Mimi đã đi các địa điểm ~\{1, 2, 4, 5\}~ ở Tây Ninh, do đó Gấu sẽ dắt Mimi đi chơi ở địa điểm ~\{3\}~ ở Long An.
• Vào ngày $2$, do Mimi đã đi các địa điểm ~\{3, 7\}~ ở Tây Ninh, do đó Gấu sẽ dắt Mimi đi các địa điểm ~\{1, 2, 4, 5\}~ ở Long An.
• Vào ngày $3$, do Mimi đã đi địa điểm ~\{1\}~ ở Tây Ninh, do đó Gấu sẽ dắt Mimi đi chơi ở các địa điểm ~\{4, 5\}~ ở Long An.

Tính điểm

• Subtask 1 (20% số điểm): $1 \leq n, q \leq 1000$.
• Subtask 2 (10% số điểm): Luôn có đường nối giữa hai địa diểm ~i~ và ~i+1~ ở hai tỉnh.
• Subtask 3 (20% số điểm): Trong tất cả ngày đi chơi ~d_i = k_i = C~ với ~C~ là hằng số.
• Subtask 4 (50% số điểm): Không có ràng buộc gì thêm.