PVHOI3

Chắc nhiều bạn đã biết, ngoài niềm đam mê bất tận với trà sữa, GSPVH còn rất ham thích gắp thú bông. Đã thành thói quen, mỗi khi ghé thăm trung tâm thương mại, khu vui chơi hay công viên nào mà có máy gắp thú, GS ắt phải trổ tài với dăm ba đồng tiền lẻ. Nói là tiền lẻ thôi chớ đồng nào cũng màu hồng màu xanh cả. Trong cuộc sống hiện đại ngày nay, thú bông có nhiều lợi ích không thể nào bỏ qua. Những con gấu bông xinh xắn, dễ thương luôn khiến ai ai cũng cảm thấy nhẹ nhàng, êm ái mỗi khi ngắm nhìn chúng. Chúng giúp chúng ta xua tan bao áp lực bộn bề của cuộc sống vốn ngập tràn mỏi mệt. Nhiều chú gấu bông còn có cặp má phính véo thì thích miễn chê rồi. Vào mùa đông lạnh giá, gấu bông như chiếc lò sưởi giúp chúng ta ấm áp cả thể chất lẫn tinh thần. Chỉ cần dang rộng vòng tay ôm lấy một chú gấu bông to lớn, những đêm dài lạnh lẽo nơi Hà Nội chỉ 8 độ C sẽ là những giấc ngủ ngon trong chiếc mền ấm êm. Kể ra thì gấu bông cũng có nhiều cái hơn một số loài gấu khác ấy chứ nhỉ. Thứ nhất, gấu bông không khiến bạn phải lo “đau ví”. Một khi đã gắp về rồi thì gấu sẽ luôn tươi tắn, vui cười và cặp má thì lúc nào cũng bầu bĩnh; trong khi với một số loài gấu khác, nếu không được chăm bón bằng trà sữa, bỏng ngô CGV và bổ sung vitamin hẹn hò thường xuyên, gấu sẽ chuyển sang chế độ cau có, giận dỗi. Và tất nhiên, chi phí cho trà sữa hay sweetbox này tốn hơn xèng gắp gấu bông từ máy rất nhiều. Như đã nói ở trên, trong đêm đông giá lạnh, gấu bông sẽ là nguồn nhiệt sưởi ấm tấm lòng, ấy nhưng, nếu ôm một số loài gấu khác, có khi bạn sẽ còn lạnh hơn ấy chứ. Và quan trọng nhất, ngôn ngữ của loài gấu bông không có những từ “phụ tình”, “phổi bạn” hay “thay lòng đổi dạ”. Gấu bông luôn sẵn sàng ở bên bạn mãi mãi, chứ ở một số loài gấu khác thì lắm lúc không phải như vậy.

Thôi nào, cuộc chia tay của những chú/con gấu không làm bằng bông thì hãy còn nhiều lắm. Giờ hãy quay về với cửa hàng gắp thú ưa thích của GSPVH đã.

Khu vui chơi tại chợ đêm Oileh ở quận Chải Hâu có một chiếc máy gắp thú với vô vàn con thú bông sặc sỡ. Để tri ân những tín đồ mê gắp thú và truyền cảm hứng gắp thú bông cho thế hệ Z, chợ đêm Oileh tung ra một chương trình ưu đãi hấp dẫn. Theo đó, giá mỗi lượt chơi gắp thú được mô tả bởi hai dãy số nguyên dương \((s_{1}, s_{2}, \ldots, s_{n})\) và \((p_{0}, p_{1}, \ldots, p_{n})\). Giả sử \(\sigma\) là số tiền người chơi đã chi cho việc gắp thú trước đây, chi phí của lượt gắp thú kế tiếp được xác định như sau:

• Nếu \(0\leq \sigma < s_{1}\), giá tiền là \(p_{0}\).
• Nếu \(s_{1} \leq \sigma < s_{2}\), giá tiền là \(p_{1}\).
• Nếu \(s_{2} \leq \sigma < s_{3}\), giá tiền là \(p_{2}\).
• \(\ldots\)
• Nếu \(s_{(n - 1)} \leq \sigma < s_{n}\), giá tiền là \(p_{(n - 1)}\).
• Nếu \(s_{n} \leq \sigma\), giá tiền là \(p_n\).

Hai dãy số này thoả mãn các điều kiện \(s_{1} < s_{2}< \cdots < s_{n}\) và \(p_{0} > p_{1} > p_{2} > \ldots > p_{n}\), ý tưởng là nếu bạn gắp thú càng nhiều, lượt gắp thú tiếp theo sẽ càng rẻ.

Ví dụ, giả sử \(n = 3\) và \((s_{1}, s_{2}, s_{3}) = (20, 30, 40)\) và \((p_{0}, p_{1}, p_{2}, p_{3}) = (7, 5, 3, 2)\); giá mỗi lượt gắp thú như sau:

• Lượt gắp thú đầu tiên có giá \(p_0 = 7\). Sau lượt này, số tiền người chơi đã chi cho việc gắp thú là \(\sigma = 7 < s_{1} = 20\).
• Lượt gắp thú thứ hai có giá \(p_{0} = 7\). Sau lượt này, số tiền người chơi đã chi cho việc gắp thú là \(\sigma = 14 < s_{1} = 20\).
• Lượt gắp thú thứ ba có giá \(p_{0} = 7\). Sau lượt này, số tiền người chơi đã chi cho việc gắp thú là \(\sigma = 21 < s_{2} = 30\).
• Lượt gắp thú thứ tư có giá \(p_{1} = 5\). Sau lượt này, số tiền người chơi đã chi cho việc gắp thú là \(\sigma = 26 < s_{2} = 30\).
• Lượt gắp thú thứ năm có giá \(p_{1} = 5\). Sau lượt này, số tiền người chơi đã chi cho việc gắp thú là \(\sigma = 31 < s_{3} = 40\).
• Lượt gắp thú thứ sáu có giá \(p_{2} = 3\). Sau lượt này, số tiền người chơi đã chi cho việc gắp thú là \(\sigma = 34 < s_{3} = 40\).
• Lượt gắp thú thứ bảy có giá \(p_{2} = 3\). Sau lượt này, số tiền người chơi đã chi cho việc gắp thú là \(\sigma = 37 < s_{3} = 40\).
• Lượt gắp thú thứ tám có giá \(p_{2} = 3\). Sau lượt này, số tiền người chơi đã chi cho việc gắp thú là \(\sigma = 40 = s_{3}\).
• Kể từ lượt gắp thú thứ chín, giá mỗi lượt là \(p_{3} = 2\).

Trong máy gắp thú có một số con gấu bông. Mỗi con gấu bông có một giá trị riêng. Số lượng và giá trị của những con gấu bông bên trong máy được mô tả bởi \(m\) cặp số nguyên \((l_{1}, r_{1}), (l_{2}, r_{2}), \ldots, (l_{m}, r_{m})\) với ý nghĩa: Với mỗi bộ số \((i, j)\) thoả mãn \(1 \leq i \leq m\) và \(l_{i} \leq j \leq r_{i}\), trong máy có thêm một con gấu bông với giá trị \(j\). Chú ý rằng, nếu có nhiều bộ số \((i, j)\) với cùng một giá trị \(j\) thoả mãn các điều kiện ở trên, trong máy sẽ có nhiều con gấu cùng giá trị. Như vậy, tổng số gấu bông trong máy là \((r_{1} - l_{1} + 1) + (r_{2} - l_{2} + 1) + \cdots + (r_{m} - l_{m} + 1)\).

Ví dụ, giả sử \(m = 3\) và các bộ số lần lượt là \((2, 5), (8, 10), (10, 12)\). Khi đó, máy gồm 10 con gấu bông với giá trị lần lượt là \(2, 3, 4, 5, 8, 9, 10, 10, 11, 12\).

Với kinh nghiệm chinh chiến ở muôn vàn đấu trường gắp thú trên khắp mọi miền tổ quốc, GSPVH tự tin mình có thể gắp “bách phát bách trúng” (gắp phát nào trúng phát đó). Thế nhưng, để tránh việc nhân viên siêu thị phát hiện tài năng của GSPVH và đẩy GS ra xa đàn gấu thân yêu, GS luôn chọn gắp thú theo thứ tự giá trị từ nhỏ đến lớn. Nói cách khác, GS luôn chọn gắp con thú có giá trị nhỏ nhất trong số những con thú còn trong máy.

GSPVH đặt ra mục tiêu kiếm được số tiền \(t\) nhờ việc bán gấu gắp được (do nhà GS đã có đầy đủ gấu để ohm rùi). Do GS còn bận chuẩn bị đề thi PVHOI 3.0, GS muốn biết cần ít nhất bao nhiêu lượt gắp để số tiền kiếm được là ít nhất \(t\) (nói cách khác, tổng giá trị của những chú gấu gắp được trừ đi số tiền bỏ ra để chơi gắp thú không bé hơn \(t\)).

Để tăng độ khó cho bài toán, bạn được cho \(q\) số nguyên dương \(t_{1}, t_{2}, \ldots, t_{q}\). Với mỗi số \(t_{i}\), hãy bạn cần cho GS biết số lần chơi gắp thú ít nhất để thu về được số tiền không ít hơn \(t_{i}\).

Input

• Dòng đầu tiên chứa ba số nguyên \(n, m\) và \(q\) \((1 \leq n, m, q \leq 10^{5})\).
• Dòng thứ hai chứa \(n\) số nguyên \(s_{1}, s_{2}, \ldots, s_{n}\) \((0 < s_{1} < s_{2} < \ldots < s_{n} < 4 \cdot 10^{18} + 1)\).
• Dòng thứ ba chứa \(n + 1\) số nguyên \(p_{0}, p_{1}, p_{2}, \ldots, p_{n}\) \((4 \cdot 10^{18} + 1 > p_{0} > p_{1} > p_{2} > \ldots > p_{n} > 0)\).
• Trong \(m\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(l_{i}\) và \(r_{i}\) \((1 \leq l_{i} \leq r_{i} \leq 10^{7})\).
• Dòng cuối cùng chứa \(q\) số nguyên \(t_{1}, t_{2}, \ldots, t_{q}\) \((1 \leq t_{i} \leq 4 \cdot 10^{18})\).

Output

• Gồm một dòng duy nhất chứa \(q\) số nguyên, số thứ \(i\) trong đó là số lượt chơi tối thiểu để GS kiếm đượt số tiền không ít hơn \(t_{i}\). Nếu GS gắp hết toàn bộ thú trong máy mà vẫn không kiếm đủ số tiền như mục tiêu, in ra \(-1\).

Scoring

• Subtask \(1\) (\(13\) điểm): \(m = n = 1\), \(q \leq 1000\) và \(r_{1} \leq 1000\).
• Subtask \(2\) (\(13\) điểm): \(m = n = 1\).
• Subtask \(3\) (\(13\) điểm): \(n = 1\).
• Subtask \(4\) (\(13\) điểm): \(n \leq 10\).
• Subtask \(5\) (\(18\) điểm): Không có ràng buộc gì thêm.

Example

3 3 3
20 30 40
7 5 3 2
2 5
8 10
10 12
1 20 34

7 9 -1

Vậy là một mùa xuân Quý Mão lại về trên khắp muôn nơi. Xuân về là sự khởi đầu của bao chu kỳ mới: Đó là chu kỳ của một năm gồm \(12\) tháng, là chu kỳ \(4\) mùa xuân, hạ, thu, đông. Đó còn là chu kỳ sinh sôi, nảy nở của muôn loài. Xuân sang là lúc bao sức sống mới tràn về. Cỏ cây hoa lá chấm dứt thời kỳ ẩn mình cằn cỗi trong cái lạnh tái tê, chuyển sang giai đoạn xanh tươi rực rỡ. Hoà chung vào sự chuyển đổi của đất trời, con người cũng trở nên vui tươi yêu đời hơn. Mỗi dịp “năm hết, Tết đến”, chúng ta tạm gác lại những lo toan bộn bề, những thử thách khó khăn còn sót lại của năm cũ, hoà mình vào hương xuân phơi phới, tích luỹ năng lượng tràn trề và niềm tin về một năm mới ngập tràn tốt tươi. Bởi thế, cho dù cuộc sống ngày nay có gấp gáp và vội vã nhường nào, chúng ta vẫn ít nhiều chờ mong tới Tết và háo hức mỗi dịp xuân sang.

Mùa xuân tươi đẹp, rực rỡ, rộn rã và đầy sức sống đến thế, ấy vậy mà có người lại chỉ muốn đông ở lại mãi mà chẳng thèm xuân sang. Đó chính là Nhật Quang. Nhật Quang yêu thích mùa đông là bởi vì, Nhật Quang yêu Tuyết, và chỉ có vào mùa đông thì Tuyết mới về. Không hiểu trái tym của Nhật Quang lạnh lẽo tới đâu mà anh chàng lại có gu cô nàng dưới \(0\) độ C như vậy. Với con người ta, xuân sang là lúc tâm hồn được sưởi ấm, được thoát khỏi cái lạnh tái tê để tung tăng bay nhảy. Nhưng với Nhật Quang, thấy Tuyết tan chảy rồi dần dần biến mất, chẳng khác nào xuân sang mang ngọn lửa đốt cháy rụi con tym của chàng. Dù chán ghét xuân sang, căm thù Tết đến, nhưng thôi để giống bao người ta, Quang đành phải dọn sạch Tuyết để đặt những khóm Trúc, cành Mai trang trí khu vườn.

Khu vườn nhà Nhật Quang có dạng lưới ô vuông gồm \(r\) hàng và \(c\) cột. Các hàng được đánh số từ \(1\) đến \(r\) và các cột được đánh số từ \(1\) đến \(c\). Ô thuộc hàng \(i\) và cột \(j\) được ký hiệu là \((i, j)\). Nhật Quang dự định đặt hoa trang trí vào một số ô trong khu vườn. Vốn không muốn nhìn thấy Trúc hay Mai quá nhiều, Quang đặt ra luật sau cho việc đặt hoa trang trí: Nếu hai ô \((x_{1}, y_{1})\) và \((x_{2}, y_{2})\) thể hiện nước đi hợp lệ của quân mã trên bàn cờ, cả hai ô này không thể cùng có hoa. Nói cách khác, ít nhất một trong hai ô này phải không có hoa.

Ngoài ra, Nhật Quang còn có một dãy số đẹp \(a_{1}, a_{2}, \ldots, a_{r}\). Mỗi số trong dãy này có giá trị từ \(0\) đến \(3\). Để đặt hoa trang trí Như Ý Nhật Quang, số ô chứa hoa trên mọi hàng phải thoả mãn hai điều kiện sau:

• Nếu \(a_{i} < 3\), số ô có hoa trên hàng \(i\) phải đồng dư với \(a_{i}\) khi chia cho \(3\).
• Nếu \(a_{i} = 3\), số ô có hoa trên hàng \(i\) có thể là một giá trị bất kỳ.

Ra Tết là lúc kỳ thi học sinh giỏi quốc gia đến thật gần, Nhật Quang muốn ôn lại các bài toán đếm. Và Quang đã nghĩ ra bài toán sau: Với mỗi ô \((i, j)\) trong khu vườn, có bao nhiêu cách đặt hoa trang trí mà Nhật Quang cho là Như Ý, đồng thời ô \((i, j)\) có được đặt hoa?

Nhắc lại, hai ô \((x_{1}, y_{1})\) và \((x_{2}, y_{2})\) thể hiện nước đi hợp lệ của quân mã trên bàn cờ khi và chỉ khi \((x_{1} - x_{2})^{2} + (y_{1} - y_{2})^{2} = 5\). Hai cách đặt hoa trang trí được coi là khác nhau khi và chỉ khi tồn tại một ô có hoa ở cách này, nhưng lại không có hoa ở cách khác.

Input

• Dòng đầu tiên chứa hai số nguyên \(r\) và \(c\) \((1 \leq r \leq 60,1 \leq c \leq 10)\).
• Dòng thứ hai chứa \(r\) số nguyên \(a_{1}, a_{2}, \ldots, a_{r}\) \((0 \leq a_{i} \leq 3)\).

Output

• Gồm \(r\) dòng, mỗi dòng chứa \(c\) số nguyên. Số thứ \(j\) trên dòng thứ \(i\) là số cách đặt hoa trang trí Như Ý Nhật Quang mà ở đó ô \((i, j)\) có hoa. Do kết quả có thể rất lớn, các bạn chỉ cần in phần dư của các số này khi chia cho \(10^{9} + 19972207\).

Scoring

• Subtask \(1\) (\(14\) điểm): \(r \cdot c \leq 21\)
• Subtask \(2\) (\(8.4\) điểm): \(c = 1\)
• Subtask \(3\) (\(8.4\) điểm): \(c = 2\)
• Subtask \(4\) (\(11.2\) điểm): \(c \leq 4\)
• Subtask \(5\) (\(12.6\) điểm): \(c \leq 6\)
• Subtask \(6\) (\(15.4\) điểm): Không có ràng buộc gì thêm.

Example

3 3
1 0 3

4 4 4
2 2 2
4 2 4

Lý thuyết đồ thị là một mảng kiến thức vô cùng lớn và quan trọng bậc nhất của Toán rời rạc cũng như Lập trình thi đấu. Chính bởi vậy, đề thi học sinh giỏi quốc gia năm nào cũng chứa từ một tới hai bài toán đồ thị. Để chuẩn bị tốt nhất cho kỳ thi lớn sắp tới, hãy cùng nhau ôn lại đồ thị thông qua bài tập này nhé!

Trong bài tập này, ta chỉ xét các đồ thị vô hướng không chứa khuyên (cạnh nối một đỉnh với chính nó). Nói cách khác, đồ thị trong bài tập này có thể chứa cạnh lặp (tức giữa hai đỉnh có thể có nhiều cạnh nối), nhưng mỗi cạnh luôn nối hai đỉnh khác nhau.

Dưới đây là hình ảnh của một đồ thị vô hướng gồm \(13\) đỉnh và \(16\) cạnh:

Giờ ta xét tới khái niệm chu trình đơn. Một chu trình đơn trong đồ thị vô hướng là một tập hợp con khác rỗng \(S\) của tập hợp các cạnh trên đồ thị thoả mãn các tính chất dưới đây:

• Mọi đỉnh trên đồ thị kề với \(0\) hoặc \(2\) cạnh trong \(S\).
• Các cạnh trong \(S\) liên thông với nhau. Nói cách khác, với mọi cặp đỉnh \((u, v)\) của đồ thị sao cho cả \(u\) và \(v\) đều kề với ít nhất một cạnh thuộc \(S\), luôn tồn tại đường đi giữa \(u\) và \(v\) chỉ đi qua các cạnh thuộc \(S\).

Hình dưới đây thể hiện các chu trình đơn của đồ thị trên:

Hình dưới đây thể hiện một số tập hợp cạnh không thoả mãn các tính chất của chu trình đơn vì:

• Trong tập cạnh màu đỏ (hình góc trên bên trái), đỉnh \(4\) kề với \(4\) cạnh trong tập.
• Trong tập cạnh màu xanh (hình góc trên bên phải), đỉnh \(5\) kề với \(3\) cạnh trong tập.
• Tập cạnh màu tím (hình góc dưới bên trái) không thoả mãn điều kiện liên thông.
• Trong tập cạnh màu cam (hình góc dưới bên phải), đỉnh \(10\) kề với \(1\) cạnh trong tập.

Cây là một đồ thị vô hướng liên thông và không có chu trình. Một cây gồm \(n\) đỉnh luôn có chính xác \(n - 1\) cạnh.

Trong bài tập này, bạn được cho một cây gồm \(n\) đỉnh. Các đỉnh được đánh số từ \(1\) đến \(n\), các cạnh được đánh số từ \(1\) đến \(n - 1\). Cạnh thứ \(i\) nối hai đỉnh \(x_{i}\) và \(y_{i}\). Bạn cần trả lời \(q\) câu hỏi. Trong mỗi câu hỏi, bạn được cho sáu số nguyên \(e_{1}, u_{1}, v_{1}, e_{2}, u_{2}, v_{2}\) thoả mãn \(1 \leq e_{1}, e_{2} < n, 1 \leq u_{1}, v_{1}, u_{2}, v_{2} \leq n, e_{1} \neq e_{2}, u_{1} \neq v_{1}\) và \(u_{2} \neq v_{2}\). Bạn cần xây dựng một đồ thị mới bằng cách lấy cây ban đầu, xoá đi hai cạnh \(e_{1}\) và \(e_{2}\) đồng thời thêm hai cạnh \((u_{1}, v_{1})\) và \((u_{2}, v_{2})\), sau đó đếm số chu trình đơn trong đồ thị mới này. Chú ý rằng, cây ban đầu không bị biến đổi trong suốt các câu hỏi. Đồ thị trong mỗi câu hỏi đều được xây dựng từ cây ban đầu, với hai cạnh bị xoá đi và hai cạnh được thêm mới.

Để giảm kích thước file dữ liệu và file kết quả, thay vì cho trực tiếp các tham số và yêu cầu in kết quả của mọi câu hỏi, bạn cần xét đoạn mã nguồn sau:

const int MOD = (int)1e9 + 19972207;
int cur = seed;
int getRandom(int n) {
    cur = (1LL * mul * cur + add) % MOD;
    return 1 + cur % n;
}
int gspvhcute(void) {
    int res = 0;
    for (int i = 1; i <= q; i++) {
        int e1 = getRandom(n - 1);
        int u1 = getRandom(n); int v1 = getRandom(n);
        int e2 = getRandom(n - 1);
        int u2 = getRandom(n); int v2 = getRandom(n);
        int tmp = e1 == e2 || u1 == v1 || u2 == v2 
                ? MOD - 1 : query(e1, u1, v1, e2, u2, v2);
        res = (227LL * res + tmp) % MOD;
    }
    return res;
}

Trong đoạn mã nguồn trên, hàm query(e1, u1, v1, e2, u2, v2) nhận vào sáu tham số và trả về một số nguyên, là số chu trình đơn trong câu hỏi với các tham số \(e_{1}, u_{1}, v_{1}, e_{2}, u_{2}, v_{2}\) theo định nghĩa ở trên. Bạn được cho biết giá trị của các biến seed, mul, add trong đoạn mã nguồn ở trên; hãy xác định kết quả trả về của hàm gspvhcute.

Vui lòng xem kỹ phần giải thích để hiểu rõ hơn về đoạn mã nguồn này.

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 số nguyên \(n\) \((2 \leq n \leq 150000)\).
• Trong \(n - 1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_{i}\) và \(y_{i}\) \((1 \leq x_{i}, y_{i} \leq n)\) mô tả cạnh thứ \(i\) của cây ban đầu. Dữ liệu vào đảm bảo \(n - 1\) cạnh này tạo thành cây.
• Dòng cuối cùng chứa bốn số nguyên \(q, seed, mul, add\) \((1 \leq q \leq 5555555,1 \leq seed, mul, add \leq 10^{9})\) lần lượt là số câu hỏi và giá trị của các biến trong đoạn mã nguồn ở trên.

Output

• In ra một số nguyên duy nhất là kết quả trả về của hàm gspvhcute.

Scoring

• Subtask \(1\) (\(12\) điểm): \(n \leq 16\) và \(q \leq 89\)
• Subtask \(2\) (\(12\) điểm): Trong cây ban đầu, mỗi đỉnh kề với ít hơn ba đỉnh khác.
• Subtask \(3\) (\(7.2\) điểm): \(n \leq 50\) và \(q \leq 7000\)
• Subtask \(4\) (\(7.2\) điểm): \(n \leq 3000\) và \(q \leq 40000\)
• Subtask \(5\) (\(9.6\) điểm): \(q \leq 200000\)
• Subtask \(6\) (\(12\) điểm): Không có ràng buộc gì thêm.

Example

1
10
1 4
8 9
7 9
3 4
3 9
2 9
3 10
1 5
1 6
3 22 7 1997

51528

Có một ma trận dạng lưới ô vuông gồm \(m\) hàng và \(n\) cột. Các hàng được đánh số từ \(1\) đến \(m\) theo thứ tự từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(n\) theo thứ tự từ trái qua phải. Ô nằm trên hàng \(i\) và cột \(j\) được ký hiệu là \((i, j)\). Một số ô trên lưới có chứa chướng ngại vật, các ô còn lại là ô trống.

Có một con robot di chuyển trên lưới này. Vị trí xuất phát và vị trí kết thúc của con robot là những ô trống đã được cố định từ trước. Con robot được cài sẵn một chuỗi lệnh điều khiển là một xâu ký tự \(C\). Mỗi lệnh của chuỗi là một trong các ký tự U, D, L, R, H. Gọi vị trí hiện tại của robot là \((i, j)\). Ý nghĩa của từng ký tự lệnh như sau:

• U: Đi lên trên \(1\) bước tới ô \((i - 1, j)\)
• D: Đi xuống dưới \(1\) bước tới ô \((i + 1, j)\)
• L: Đi sang trái \(1\) bước tới ô \((i, j - 1)\)
• R: Đi sang phải \(1\) bước tới ô \((i, j + 1)\)
• H: Đứng yên tại ô \((i, j)\)

Con robot sẽ lần lượt thực hiện các lệnh trong chuỗi lệnh \(C\). Chú ý rằng, nếu một lệnh làm con robot đi ra ngoài bảng hoặc đi vào một ô có chướng ngại vật, con robot sẽ bỏ qua và không thực hiện lệnh di chuyển này.

Người ta nhận thấy rằng, nếu xuất phát tại vị trí đã chọn, sau khi thực hiện hết các lệnh trong chuỗi lệnh \(C\), con robot có thể không dừng lại ở vị trí kết thúc đã chọn. Vì vậy, ta cần sửa lại xâu ký tự \(C\) để con robot sẽ dừng lại tại đúng vị trí kết thúc mong muốn sau khi kết thúc thực hiện chuỗi lệnh \(C\). Trong mỗi phép biến đổi, bạn được thực hiện một trong ba thao tác sau:

• Chèn thêm một lệnh vào chuỗi \(C\) ở một vị trí bất kỳ.
• Thay đổi một lệnh bất kỳ trong chuỗi \(C\).
• Xoá đi một chuỗi con liên tiếp bất kỳ của chuỗi \(C\).

Hãy sử dụng ít phép biến đổi nhất có thể để với chuỗi lệnh \(C\), robot sẽ bắt đầu ở vị trí xuất phát đã chọn và kết thúc ở vị trí kết thúc đã chọn. Chú ý rằng, bạn không cần cực tiểu hoá số bước di chuyển của robot, chỉ cần số bước biến đổi chuỗi lệnh là nhỏ nhất có thể. Các ô xuất phát và kết thúc của robot là các ô trống. Trên hành trình của mình, robot có thể đi qua những ô này hay bất kỳ ô trống nào khác một số lần tuỳ ý.

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 \(m\) và \(n\) \((1 \leq m, n \leq 175)\).
• Trong \(m\) dòng tiếp theo, mỗi dòng chứa một xâu ký tự độ dài \(n\) mô tả một hàng của bảng. Mỗi ký tự của những xâu này có thể là . (dấu chấm thể hiện ô trống), # (ô có chướng ngại vật), S (vị trí xuất phát của robot), E (vị trí kết thúc của robot). Dữ liệu vào đảm bảo có chính xác một chữ S và chính xác một chữ E trong lưới.
• Dòng cuối cùng chứa một xâu ký tự mô tả chuỗi lệnh \(C\) được cài đặt trong robot. Xâu ký tự này chỉ chứa từ 1 đến 300 ký tự, là các chữ cái U, D, L, R và H.

Output

Nếu không tồn tại chuỗi lệnh nào giúp robot đi từ vị trí xuất phát tới vị trí kết thúc, in ra số \(-1\) duy nhất. Ngược lại, dòng đầu tiên chứa số nguyên k là số bước biến đổi chuỗi lệnh tối thiểu. Trong k dòng tiếp theo, mỗi dòng thể hiện một phép biến đổi theo một trong ba khuôn dạng sau:

• INS p c (với \(0 \leq p \leq |C|\) và \(c\) là một trong các chữ cái U, D, L, R và H): Chèn ký tự \(c\) vào sau vị trí \(p\) của chuỗi lệnh. Nếu \(p = 0\), ký tự được chèn vào đầu chuỗi lệnh. Nếu \(p = |C|\), ký tự được chèn vào cuối chuỗi lệnh.
• REP p c (với \(1 \leq p \leq |C|\) và \(c\) là một trong các chữ cái U, D, L, R và H): Thay ký tự ở vị trí \(p\) bởi ký tự \(c\).
• DEL l r (với \(1 \leq l \leq r \leq |C|\)): Xoá đi đoạn lệnh liên tiếp từ vị trí \(l\) tới vị trí \(r\).

Ở đây, \(|C|\) là độ dài chuỗi lệnh trước khi phép biến đổi diễn ra. Chú ý rằng, sau mỗi phép biến đổi, các ký tự của chuỗi lệnh được đánh số lại từ 1.

Nếu có nhiều phương án biến đổi chuỗi lệnh tối ưu, bạn được đưa ra một phương án bất kỳ.

Scoring

Bộ test của bài được chia làm các subtask như sau:

• Subtask \(1\) (\(14\) điểm): \(m = 1\).
• Subtask \(2\) (\(10.5\) điểm): Chuỗi lệnh \(C\) chỉ chứa ký tự H.
• Subtask \(3\) (\(10.5\) điểm): Dữ liệu vào đảm bảo tồn tại một phương án biến đổi tối ưu mà không cần sử dụng phép biến đổi DEL (xoá một đoạn liên tiếp).
• Subtask \(4\) (\(10.5\) điểm): \(m, n \leq 20\) và chuỗi lệnh ban đầu có không quá \(50\) ký tự.
• Subtask \(5\) (\(10.5\) điểm): \(m,n \leq 50\) và chuỗi lệnh ban đầu có không quá \(100\) ký tự.
• Subtask \(6\) (\(14\) điểm): Không có ràng buộc gì thêm.

Với mỗi test, bạn được 50% số điểm nếu tìm ra số bước biến đổi tối thiểu mà không đưa ra được phương án biến đổi.

Example

4
3 5
....E
S#...
..#..
LRRRDDULLDU

3
REP 1 U
DEL 5 10
INS 5 R

3
3 5
.....
...SE
.....
LLLRRRRRUUD

0

2
3 5
.#..E
..#..
S..#.
HHHHHHHHHHH

-1

Cho bốn số nguyên dương \(n, k, a\) và \(b\). Hãy đếm số dãy số nguyên dương \(x_{1}, x_{2}, \ldots, x_{n}\) sao cho:

• Với mọi \(1 \leq i \leq n, a \leq x_{i} \leq b\).
• Bội số chung nhỏ nhất của các số \(x_{1}, x_{2}, \ldots, x_{n}\) chia hết cho \(k\).

Do số lượng dãy có thể rất lớn, bạn chỉ cần in ra kết quả theo modulo \(998244353\).

Input

• Gồm một dòng duy nhất chứa bốn số nguyên \(n, k, a\) và \(b\) \((1 \leq n \leq 227,1 \leq k \leq 10^{14}, 1 \leq a \leq b \leq 10^{14})\).

Output

• Gồm một số nguyên duy nhất là kết quả của bài toán nêu trên theo modulo \(998244353\).

Scoring

• Subtask \(1\) (\(7\) điểm): \(k = 1\)
• Subtask \(2\) (\(8\) điểm): \(n \leq 5, b \leq 30\) và \(k \leq 30\).
• Subtask \(3\) (\(9\) điểm): \(n \leq 5\) và \(b - a \leq 30\)
• Subtask \(4\) (\(10\) điểm): \(k\) là số nguyên tố
• Subtask \(5\) (\(16\) điểm): \(b \leq 10^{7}\) và \(k \leq 10^{7}\)
• Subtask \(6\) (\(20\) điểm): Không có ràng buộc gì thêm.

Example

2 6 10 14

9

3 5 7 9

0

Cho dãy số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\). Bạn cần thực hiện \(q\) thao tác trên dãy số này, mỗi thao tác thuộc một trong ba dạng dưới đây:

• A l r x y: Xét các số \(a_{l}, a_{l + 1}, a_{l+2}, \ldots, a_{r}\); bạn cần nhân các số này với lần lượt các giá trị \(x, x + y, x + 2 \cdot y, \ldots, x + (r-l) \cdot y\). Nói cách khác, với mọi chỉ số \(i\) sao cho \(l \leq i \leq r\), ta thay phần thử \(a_{i}\) bởi \(a_{i} \cdot (x + (i-l) \cdot y)\).
• G l r x y: Xét các số \(a_{l}, a_{l + 1}, a_{l+2}, \ldots, a_{r}\); bạn cần nhân các số này với lần lượt các giá trị \(x, x \cdot y, x \cdot y^{2}, \ldots, x \cdot y^{r - l}\). Nói cách khác, với mọi chỉ số \(i\) sao cho \(l \leq i \leq r\), ta thay phần thử \(a_{i}\) bởi \(a_{i} \cdot x \cdot y^{i - l}\).
• C l r: Xét số nguyên dương \(P = a_{l} \cdot a_{l + 1} \cdot a_{l + 2} \cdot \ldots \cdot a_{r}\); bạn cần tìm số chữ số không ở ngoài cùng bên phải khi viết số \(P\) trong hệ thập phân. Nói cách khác, bạn cần tìm số nguyên không âm \(k\) lớn nhất sao cho \(P\) chia hết cho \(10^{k}\).

Bạn hãy viết chương trình thực hiện các yêu cầu trên.

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à \(q\) \((1 \leq n, q \leq 200311)\)
• Dòng thứ ba chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_i \leq 10^{6})\) mô tả dãy số ban đầu.
• Trong \(q\) dòng cuối cùng, mỗi dòng thể hiện một thao tác thuộc một trong ba dạng sau:
  • A l r x y với \(1 \leq l \leq r \leq n, 1 \leq x \leq 10^{6}\) và \(0 \leq y \leq 10^{6}\)
  • G l r x y với \(1 \leq l \leq r \leq n\) và \(1 \leq x, y \leq 10^{6}\)
  • C l r với \(1 \leq l \leq r \leq n\)

Output

• Với mỗi thao tác thuộc dạng \(C\), in ra kết quả trên một dòng.

Scoring

• Subtask \(1\) (\(10\) điểm): n,q≤1000
• Subtask \(2\) (\(10\) điểm): Mọi thao tác loại A có \(y = 0\) và mọi thao tác loại G có \(y = 1\).
• Subtask \(3\) (\(10\) điểm): Mọi thao tác loại A có \(y = 0\).
• Subtask \(4\) (\(10\) điểm): Mọi thao tác loại A có \(y = 1\).
• Subtask \(5\) (\(10\) điểm): Mọi thao tác loại C có \(l = 1\) và \(r = n\).
• Subtask \(6\) (\(10\) điểm): Không có ràng buộc gì thêm.

Example

1
7 5
2 2 7 1 9 9 7
A 2 4 6 3
G 4 6 5 2
C 1 5
C 2 6
C 3 7

2 3 3