Bacteria

View as PDF

Submit solution

Points: 1.90 (partial)
Time limit: 35.0s
Memory limit: 64M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Thời gian này là một giai đoạn vô cùng bận rộn với IPSC (Institute of Parasitic and Symbiotic Creatures). Họ vừa phát hiện ra một chủng loại vi khuẩn mới, được đặt tên là virus ~R~, và họ đang cố gắng tìm kiếm thông tin về loại vi khuẩn vô cùng kỳ diệu này.

Việc đầu tiên mà các nhà nghiên cứu phải làm là nghiên cứu sự sinh sôi của loài vi khuẩn này. Các nhà nghiên cứu đã tìm hiểu được những điều sau về loài vi khuẩn này:

Loại vi khuẩn sống thành ~N~ bầy, đánh số từ ~0~ đến ~N-1~. Ban đầu mỗi bầy có đúng ~1~ vi khuẩn Mỗi giây, số lượng vi khuẩn trong mỗi bầy lại thay đổi: Một số có thể chết, sinh sản thêm, hoặc di chuyển sang bầy khác. Những thay đổi này luôn tuân theo một quy luật có sẵn. Có ~M~ quy luật đánh số từ ~0~ đến M-1. Ở giây thứ ~S~, quy luật thứ ~(S-1) \% M~ sẽ được thực hiện Khi có ~K~ vi khuẩn trong cùng ~1~ bầy, ~K~ vi khuẩn này sẽ kết hợp với nhau, tạo thành một loài mới và bay mất. Các nhà khoa học đã xác định được ~K = 5^{96}~ ~(= 1262 \dots 625)~.

Nhiệm vụ của bạn là tính xem, sau ~T~ giây, lượng vi khuẩn trong mỗi bầy là bao nhiêu.

Input

  • Dòng ~1~: ~N~, ~M~, ~T~. ~(N \leq 100~, ~M \leq 1000~, ~T \leq 10^{18})~
  • Dòng ~2~: ~K~ (trong tất cả các test, ~K = 5^{96}~. Trong test ví dụ, ~K~ nhỏ hơn để bạn dễ hình dung).
  • ~M~ dòng tiếp, mỗi dòng mô tả ~1~ quy luật. Mỗi quy luật thuộc ~1~ trong các dạng sau:
    • die ~i~ ~0~: Tất cả các vi khuẩn trong bầy thứ ~i~ chết
    • reproduce ~i~ ~k~: Lượng vi khuẩn trong bầy thứ ~i~ tăng lên gấp ~k~ lần ~(k \leq 100)~
    • copy ~i~ ~j~: Số vi khuẩn trong bầy ~i~ tăng thêm ~1~ lượng bằng số vi khuẩn trong bầy ~j~
    • teleport ~i~ ~j~: Tất cả các vi khuẩn trong bầy ~j~ di chuyển sang bầy ~i~
    • swap ~i~ ~j~: Các vi khuẩn trong bầy ~i~ di chuyển sang bầy ~j~, và đồng thời, các vi khuẩn trong bầy ~j~ cũng di chuyển sang bầy ~i~
    • merry-go-round ~0~ ~0~: Các vi khuẩn ở bầy ~i~ di chuyển sang bầy ~(i + 1)~ % ~N~. Các di chuyển xảy ra đồng thời.

Output

Gồm ~N~ dòng, dòng thứ ~i~ (đánh số từ ~1)~ ghi số vi khuẩn ở bầy i-1, sau ~T~ đơn vị thời gian.

Sample Input

8 6 11
7
reproduce 2 5 
copy 4 2
die 1 0
merry-go-round 0 0
teleport 5 3
swap 0 2

Sample Output

1
0
0
0
0
4
4
1

Note

Thời điểm Thay đổi Bầy 0 Bầy 1 Bầy 2 Bầy 3 Bầy 4 Bầy 5 Bầy 6 Bầy 7
Ban đầu 1 1 1 1 1 1 1 1
Giây 1 reproduce 2 5 1 1 5 1 1 1 1 1
Giây 2 copy 4 2 1 1 5 1 6 1 1 1
Giây 3 die 1 0 1 0 5 1 6 1 1 1
Giây 4 merry-go-round 0 0 1 1 0 5 1 6 1 1
Giây 5 teleport 5 3 1 1 0 0 1 4 1 1
Giây 6 swap 0 2 0 1 1 0 1 4 1 1
Giây 7 reproduce 2 5 0 1 5 0 1 4 1 1
Giây 8 copy 4 2 0 1 5 0 6 4 1 1
Giây 9 die 1 0 0 0 5 0 6 4 1 1
Giây 10 merry-go-round 0 0 1 0 0 5 0 6 4 1
Giây 11 teleport 5 3 1 0 0 0 0 4 4 1

Comments

Please read the guidelines before commenting.



  • 9
    bubu2006   commented on April 19, 2022, 9:59 p.m.

    link đến official solution của bài cho các bạn chưa giải được: https://ipsc.ksp.sk/2003/real/solutions/h.html