Giải bài trực tuyến

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.....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 <= 100, M <= 1000, T <= 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 <= 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.

Example

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

Output:
1
0
0
0
0
4
4
1

Giải thích

reproduce 2 5

copy 4 2

die 1 0

merry-go-round 0 0

teleport 5 3

swap 0 2

reproduce 2 5

copy 4 2

die 1 0

merry-go-round 0 0

teleport 5 3