Nhân kỉ niệm tròn hai tuần ngày Zi bước sang tuổi \(17\), cũng là ngày ngiu Zi lên \(17\) trong hai tuần tới, Zi muốn mua cây đàn Kalimba dành tặng tình yêu.

Chú thích: Trong câu chuyện tình dưới đây, cả hai nhân vật chính đều là nữ. Tuy nhiên, theo như thông tin mới nhất mà tác giả nhận được, cặp đôi này chẳng mặn nồng lắm đâu. Chẳng qua là chưa được anh lào ngó tới nên đành iu tạm cho zui z thôi á, chứ cũng hơi tí là ctay ầm ầm ấy mà. Nói vậy để những bạn nào làm bài này đừng hiểu rằng đây là chuyện Bách Hợp nhé.

Zi xuất thân từ thành phố Buôn Ma Thuật. Nơi đây được mệnh danh là xử sở cà phê mặc dù ở đây có nhiều loại cà chẳng hề phê cho lắm. Thành phố có \(n\) khu nhà, được đánh số từ \(1\) đến \(n\). \(n\) khu nhà được kết nối bởi \(m\) con đường hai chiều: các con đường được đánh số từ \(1\) tới \(n\), con đường thứ \(i\) kết nối khu nhà \(u_i\) với khu nhà \(v_i\) và có độ dài là \(c_i\). \(m\) con đường này kết nối thông suốt \(n\) khu nhà; nói cách khác, từ một khu nhà bất kì luôn luôn tồn tại cách để đi sang một khu nhà khác thông qua một vài con đường. Điều này là để những cô gái như Zi, Lin hay VHA; dù có thay ngiu nhìu đến mấy thì cũng yên tâm rằng mình luôn có thể theo được chân ái.

Lại nói về sinh nhật sắp tới của ngiu, dù quyết tâm cao độ, Zi vẫn khó lòng biến được giấc mơ cây đàn Kalimba của ngiu trở thành hiện thực. Số là, cả thành phố Buôn Ma Thuật chỉ có duy nhất một cửa hàng bán đàn, mà nhà Zi, nhà ngiu và cửa hàng đàn lại thuộc ba khu dân cư khác nhau (đôi một phân biệt): nhà Zi ở khu dân cư \(z\), nhà ngiu Zi ở khu dân cư \(l\) và cửa hàng bán đàn thuộc khu dân cư \(s\). Bởi thế, việc đi từ nhà tới cửa hàng bán đàn rồi lại bê đàn từ đó tới nhà ngiu tiêu tốn quá nhiều năng lượng, mà điều này thì lại quá khó với Zi. À, chỗ này tác giả lại phải đính chính thêm rằng, Zi là một cô gái ``dân chài'', bo đì đẹp, nên chỉ thích hợp để tạo dáng hoy, chứ để Zi mà phải làm việc bê vác nặng nhọc thì tội nghiệp đáng thương lắm. Cái này tác giả phải nói rõ ra như vậy là vì sợ nhiều người khi đọc tới chỗ này lại nghĩ rằng Zi nhác đi bộ là do Zi b... À mà thôi, b... gì gì đấy thì Zi cũng không phải thế đâu, hihi :3.

Sau một hồi sử dụng vốn thuật toán sơ đẳng của mình, thần đồng thuật tán Zi đã nghĩ ra một cách như sau: Zi sẽ không tới tận cửa hàng đàn nữa, mà thay vào đó chọn ra một khu dân cư \(x\) và yêu cầu cửa hàng mang cây đàn tới đây. Zi sẽ chỉ đi từ nhà mình (ở khu dân cư \(z\)) tới khu dân cư \(x\) để lấy cây đàn và đem tới nhà ngiu (ở khu dân cư \(l\)). Để không phải đi bộ nhiều, Zi chọn khu dân cư \(x\) sao cho việc đi qua đây không làm tăng quãng đường tối thiểu cần đi (nói cách khác, \(x\) phải nằm trên một đường đi ngắn nhất nào đó từ \(z\) đến \(l\)). Đồng thời, để cực tiểu hóa phí giao hàng, khu dân cư \(x\) này phải gần cửa hàng đàn (ở khu dân cư \(s\)) nhất có thể. Nếu vẫn có nhiều khu dân cư \(x\) như vậy, hãy chọn khu dân cư có chỉ số \(x\) nhỏ nhất.

Yêu cầu: Cho biết ba khu dân cư phân biệt \(z\), \(l\) và \(s\) lần lượt là nhà của Zi, nhà của ngiu Zi và địa chỉ cửa hàng đàn duy nhất trong thành phố, hãy xác định khu dân cư \(x\) mà Zi chọn làm địa điểm giao hàng, theo quy tắc ở trên.

Đó là yêu cầu riêng với Zi trong thời điểm hiện tại, chứ còn như các bạn biết đấy, ngiu của Zi thay đổi nhanh như nào thì ứ ai đoán trước được đâu. Mà đâu chỉ riêng Zi, như ở hàng xóm của Zi có nam thanh niên giấu giới tính DXMH nào đấy, hội ngiu cũ đã đủ 5 chị em rồi. Thế nên để phòng xa, GSPVH đã viết chương trình tính sẵn. Theo đó, thay vì chỉ giải quyết bài toán với một bộ ba khu dân cư \((z, l, s)\) ở thời điểm hiện tại, GS còn tạo ngẫu nhiên ra một số bộ ba khác. Với mỗi bộ ba như vậy, GS lại tìm khu dân cư \(x\) tương ứng.

Chương trình của GSPVH có dạng như sau:

int seed;
int getRandom(void) {
    seed = (1997LL * seed + 227) \% 1000003;
    return seed;
}

int res = 0;
for (int i = 1; i <= q; i++) {
    int z = getRandom() \% n + 1;
    int l = getRandom() \% n + 1;
    int s = getRandom() \% n + 1;

    int x;
    if (z == l || l == s || s == z) x = 22071997;
    else x = answer(z, l, s);

    res = ((1LL * res << 30) ^ x) \% 998244353;
}
cout << res << endl;

Trong đoạn code trên, n là số khu dân cư trong thành phố, các giá trị q và giá trị ban đầu của seed được nhập vào từ file input, và int answer(int z, int l, int s) là hàm trả về khu dân cư \(x\) được chọn làm nơi giao và nhận đàn theo tiêu chuẩn của Zi) khi biết ba khu dân cư \(z\), \(l\) và \(s\).

Hãy xác định giá trị của biến res được in ra.

Input

• Dòng đầu tiên chứa số nguyên \(\theta\) \((1 \leq \theta \leq 6)\) là số thứ tự của subtask chứa test này.

• Dòng thứ hai chứa hai số nguyên \(n\) và \(m\) \((1 \leq m < n \leq 3 \cdot 10^5)\), lần lượt là số khu dân cư và số con đường trong thành phố Buôn Ma Thuật.

• Trong \(m\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(u_i\), \(v_i\) và \(c_i\) \((1 \leq u_i, v_i \leq n, 1 \leq c_i \leq 10)\) mô tả con đường thứ \(i\).

• Dòng cuối cùng chứa hai số nguyên \(q\) và \(seed\) \((1 \leq q \leq 6 \cdot 10^6, 0 \leq seed \leq 10^9)\) là các giá trị đầu vào của biên q và biến seed trong đoạn code của GSPVH.

Output

• In ra một số nguyên duy nhất là giá trị của biến res được in ra trong đoạn code của GSPVH.

Scoring

• Subtask \(1\) (\(18\) điểm): \(n \leq 5000\), \(q \leq 5000\), \(m = n - 1\) và \(m\) con đường tạo thành cây (không tạo thành chu trình).
• Subtask \(2\) (\(18\) điểm): \(q \leq 200\), \(m = n - 1\) và \(m\) con đường tạo thành cây (không tạo thành chu trình).
• Subtask \(3\) (\(15\) điểm): Không có khu dân cư nào kề với nhiều hơn \(2\) con đường.
• Subtask \(4\) (\(15\) điểm): \(q \leq 400000\), \(m = n - 1\) và \(m\) con đường tạo thành cây nhị phân đầy đủ.
• Subtask \(5\) (\(17\) điểm): \(q \leq 400000\).
• Subtask \(6\) (\(17\) điểm): Không có ràng buộc gì thêm.

Example

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

140294767