Contest giao lưu lớp 10 các trường Chuyên (Lần 5)

Một nhóm học sinh đang nghiên cứu để chế tạo và lập trình một con robot. Các bạn đã tạo ra một sa bàn là một bảng hình chữ nhật kích thước \(N \times M\), với hàng được đánh số từ \(1\) đến \(N\) từ trên xuống dưới và cột được đánh số từ \(1\) đến \(M\) từ trái sang phải. Ô nằm ở vị trí giao của hàng \(X\) và cột \(Y\) gọi là ô \((X, Y)\). Ban đầu, robot được đặt ở góc trái trên của bảng, tức ô \((1, 1)\). Trên bảng, các bạn đã đặt \(K\) vật cản, vật cản thứ \(i\) được đặt ở ô \((X_i, Y_i)\).

Robot có thể được điều khiển bằng một chuỗi gồm \(Q\) lệnh. Lệnh thứ \(i\) trong các lệnh này sẽ yêu cầu robot đi theo hướng \(D_i\) (lên, xuống, sang trái, sang phải) \(C_i\) ô. Tuy nhiên, nếu thấy trước mặt là vật cản hoặc rìa của sa bàn, robot sẽ dừng lại và chuyển sang thực hiện lệnh tiếp theo trong chuỗi.

Các bạn học sinh đang lập trình để robot đánh dấu và tự đếm số lượng ô trên sa bàn mà nó đã đi qua ít nhất một lần. Tuy nhiên, các bạn không chắc chắn rằng mình đã lập trình đúng hay không. Do đó, các bạn cho bạn biết các thông tin về sa bàn, các vật cản và chuỗi lệnh mà robot cần thực thi, sau đó nhờ bạn tính toán chính xác số ô mà robot đã đi qua ít nhất một lần (tính cả ô xuất phát). Bạn hãy giúp nhóm học sinh thực hiện yêu cầu này nhé.

Input

• Dòng đầu tiên gồm bốn số nguyên \(N, M, K, Q\) (\(1 \le N, M \le 10^7\), \(N \times M \le 10^7\), \(0 \le K \le 3 \times 10^5\), \(1 \le Q \le 3 \times 10^5\)).
• \(K\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên dương \(X_i, Y_i\) (\(1 \le X_i \le N, 1 \le Y_i \le M\)). Dữ liệu đầu vào đảm bảo vị trí tất cả các vật cản đôi một phân biệt và ô \((1, 1)\) không có vật cản.
• \(Q\) dòng tiếp theo, dòng thứ \(i\) gồm một ký tự \(D_i\) và một số nguyên dương \(C_i\) (\(D_i \in \{L, R, U, D\}\), \(1 \le C_i \le 10^7\)):
  • Nếu \(D_i = U\), robot sẽ di chuyển lên trên.
  • Nếu \(D_i = D\), robot sẽ di chuyển xuống dưới.
  • Nếu \(D_i = L\), robot sẽ di chuyển sang trái.
  • Nếu \(D_i = R\), robot sẽ di chuyển sang phải.

Output

• Một số nguyên duy nhất là số ô mà robot đã đi qua ít nhất một lần.

Example

3 3 2 5
1 3
3 2
R 2
D 3
L 1
D 2
U 2

5

Scoring

• \(30\%\) số điểm có \(N = 1\).
• \(30\%\) số điểm khác có \(N, M \le 200\).
• \(20\%\) số điểm khác có \(N, M \le 3000\).
• \(20\%\) số điểm còn lại không có giới hạn gì thêm.

Alice cần tạo một mật khẩu mạnh cho tài khoản mạng xã hội của cô. Cô muốn viết một chương trình tự động, chương trình này nhận vào một xâu ký tự \(S\) chỉ gồm các chữ số và chữ cái trong bảng chữ cái tiếng Anh và trả ra một xâu ký tự \(T\) là mật khẩu được tạo. Xâu \(T\) được tạo từ xâu \(S\) theo quy tắc sau đây:

• Ký tự đầu tiên của xâu \(T\) là ký tự cuối cùng của xâu \(S\).
• Tiếp theo là tổng các ký tự số trong xâu \(S\).
• Tiếp theo là các ký tự số trong xâu \(S\) được sắp xếp theo thứ tự tăng dần.
• Tiếp theo là các ký tự chữ trong xâu \(S\) theo đúng thứ tự xuất hiện trong \(S\). Nếu ký tự là chữ hoa, chuyển sang chữ thường tương ứng.
• Cuối cùng là số lượng ký tự là chữ hoa trong xâu \(S\).

Sau khi tạo được xâu \(T\), Alice tự hỏi rằng có bao nhiêu xâu \(S\) khác nhau có thể tạo ra xâu \(T\) như vậy. Bạn hãy trả lời câu hỏi này giúp Alice nhé.

Input

• Một dòng duy nhất gồm một xâu \(T\). Dữ liệu đầu vào đảm bảo xâu \(T\) được tạo thành từ ít nhất một xâu \(S\) có không quá \(10^5\) ký tự.

Output

• Một dòng duy nhất là số xâu \(S\) có thể tạo thành xâu \(T\). Vì kết quả có thể rất lớn nên chỉ cần in phần dư của nó khi chia cho \(10^9 + 7\).

Example

C422ac1

3

Scoring

• 30% số điểm có xâu \(S\) ban đầu chỉ bao gồm các chữ cái in thường và tối đa 1 ký tự số.
• 30% số điểm khác có xâu \(S\) ban đầu chỉ bao gồm các chữ cái in thường và tối đa 2 ký tự số.
• 20% số điểm khác có xâu \(S\) ban đầu có tối đa 1 ký tự số.
• 20% số điểm còn lại không có giới hạn gì thêm.

Một chuỗi siêu thị có \(N\) kho hàng được đánh số từ \(1\) đến \(N\). Ban đầu, kho hàng thứ \(i\) có \(A_i\) tấn hàng. Từ sáng sớm, có rất nhiều lượt xe chở hàng đến các kho, xe thứ \(t\) sẽ bổ sung cho các kho từ \(L_t\) đến \(R_t\), mỗi kho thêm \(X_t\) tấn hàng để chuẩn bị cho ngày mới.

Trong khi các kho đang nhận hàng, quản lý sẽ liên tục kiểm tra lượng hàng thực tế trong kho và lập kế hoạch phân phối cho ngày mới:

• Để kiểm tra lượng hàng thực tế trong các kho, quản lý sẽ hỏi các câu hỏi: tính tổng khối lượng hàng trong các kho được đánh số từ \(L\) đến \(R\).
• Để lập kế hoạch cho ngày mới, ban quản lý cần giải quyết các câu hỏi: nếu lấy hàng ở các kho liên tiếp bắt đầu từ kho được đánh số \(L\) trở về sau, thì cần lấy hàng ở tối thiểu bao nhiêu kho để có thể lấy đủ \(X\) tấn hàng, hoặc là không thể lấy đủ. Lưu ý rằng các câu hỏi này chỉ là các giả định và không thực sự lấy hàng ra khỏi kho.

Ban quản lý đã biết trước được kế hoạch nhận hàng của kho, cũng như các câu hỏi cần trả lời ở các thời điểm khác nhau. Do đó, họ đã chia quá trình nhận hàng, kiểm tra và lập kế hoạch phân phối thành \(Q\) sự kiện theo dòng thời gian, mỗi sự kiện thuộc một trong ba loại kể trên. Với mỗi sự kiện, ban quản lý sẽ tính toán được câu trả lời chính xác cho các câu hỏi.

Input

• Dòng đầu tiên gồm hai số nguyên \(N, Q\) \((1 \le N, Q \le 3 \cdot 10^5)\).
• Dòng tiếp theo gồm \(N\) số nguyên dương \(A_1, A_2, \ldots, A_N\) \((1 \le A_i \le 10^4)\).
• \(Q\) dòng tiếp theo, mỗi dòng thuộc một trong ba loại sau:
  • Mô tả sự kiện nhận hàng (loại \(1\)): 1 L R X \((1 \le L \le R \le N,\ 1 \le X \le 10^4)\).
  • Mô tả câu hỏi kiểm tra tổng (loại \(2\)): 2 L R \((1 \le L \le R \le N)\).
  • Mô tả câu hỏi lấy hàng (loại \(3\)): 3 L X \((1 \le L \le N,\ 1 \le X \le 10^5)\).

Output

• Với mỗi câu hỏi loại \(2\) và \(3\), in ra kết quả trên một dòng.
  • Với câu hỏi loại \(2\), in ra một số nguyên là tổng khối lượng hàng có trong các kho từ \(L\) đến \(R\).
  • Với câu hỏi loại \(3\), in ra:
    • \(-1\) nếu không thể lấy đủ \(X\) tấn hàng.
    • Một số nguyên dương là số kho ít nhất cần lấy nếu có thể lấy đủ hàng.

Example

3 6
1 2 3
1 1 2 1
1 2 3 2
2 1 2
2 2 3
3 1 4
3 3 10

7
10
2
-1

Scoring

• \(20\%\) số điểm có \(N, Q \le 2000\).
• \(20\%\) số điểm khác không có yêu cầu loại \(1\).
• \(20\%\) số điểm khác có yêu cầu loại \(1\) xuất hiện trước các yêu cầu loại \(2\) và \(3\).
• \(20\%\) số điểm khác không có yêu cầu loại \(3\).
• \(20\%\) số điểm còn lại không có giới hạn gì thêm.