Tại một vùng nông thôn nọ, có một bác nông dân hiền lành, chăm chỉ. Ấy thế mà thời tiết năm nay lại có vẻ thất thường làm cho bác rất lo lắng cho cây cối trong vườn bác. Khu vườn của bác có dạng một bảng hình chữ nhật kích thước ~h \times w~ ô đất. Mỗi ô đất có diện tích là $1$ đơn vị. Các cột được đánh số từ ~1~ đến ~w~ từ trái sang phải và các dòng được đánh số từ ~1~ đến ~h~ từ dưới lên trên. Ô đất ở cột $i$, dòng $j$ được kí hiệu là ~(i, j)~.

Ban đầu, mọi ô đất trong khu vườn đều có độ ẩm là ~0~. Đình là cháu bác nông dân, với kinh nghiệm làm việc dày dặn tại đài khí tượng học, Đình đã đưa ra dự báo thời tiết tại khu vườn của bác nông dân trong $n$ ngày tới. Mỗi ngày, thời tiết sẽ xảy ra một trong ba hiện tượng như sau:

1. Xảy ra mưa trong một vùng hình chữ nhật: Khi đó tất cả ô đất nằm trong vùng này sẽ tăng độ ẩm thêm $1$.
2. Xảy ra nắng gắt trong một vùng hình chữ nhật: Khi đó tất cả ô đất nằm trong vùng này sẽ giảm độ ẩm đi $1$.
3. Thời tiết ôn hòa: Tất cả ô đất đều giữ nguyên độ ẩm.

Để có thể trồng trọt trên một ô đất, ô đất ấy cần thỏa mãn giới hạn độ ẩm. Gọi $d$ là độ ẩm của một ô đất, các ô đất được chỉ xem là có thể trồng trọt được khi ~|d| \leq K~ với ~K~ là số nguyên cho trước, do tùy thuộc vào tình hình tài chính của bác nông dân. Một vùng đất có thể trồng trọt gồm các ô đất có thể trồng trọt kề cạnh nhau, bên cạnh đó bác cần có ít nhất một cái giếng đặt tại một ô đất bất kì trong vùng đất này để có thể tưới tiêu thường xuyên.

Với thông tin dự báo thời tiết được cung cấp, bạn hãy xác định tổng diện tích đất có thể trồng trọt và số lượng giếng ít nhất bác John cần xây.

Input

• Dòng đầu tiên gồm các số nguyên ~h, w, n, K~ ~(1 \leq h, w \leq 10^9, 1 \leq n \leq 2000, 0 \leq K \leq n)~ - lần lượt là kích thước khu vườn, số lượng ngày tiếp theo được dự báo thời tiết, giới hạn độ ẩm của ô đất.
• ~n~ dòng tiếp theo mô tả dự báo thời tiết trong ~n~ ngày, mỗi dòng có dạng như sau:
  • rain l b r t: Ngày có mưa trong vùng hình chữ nhật giới hạn bởi ô trái dưới ~(l, b)~ và ô phải trên ~(r, t)~
  • sun l b r t: Ngày có nắng gắt trong vùng hình chữ nhật giới hạn bởi ô trái dưới ~(l, b)~ và ô phải trên ~(r, t)~
  • mild: Thời tiết ôn hòa trên toàn khu vườn
  • Với ~l, b, r, t~ là các số nguyên sao cho ~1 \leq b \leq t \leq h, 1 \leq l \leq r \leq w~

Output

In ra hai số nguyên trên cùng một dòng ngăn cách nhau bởi dấu cách, lần lượt là tổng diện tích đất có thể trồng trọt và số lượng giếng ít nhất bác nông dân cần xây.

Scoring

• Subtask 1 ~(30\%)~: ~h, w, n \leq 200~.
• Subtask 2 ~(30\%)~: ~h, w, n \leq 2000~.
• Subtask 3 ~(40\%)~: Không có ràng buộc gì thêm.

Sample Input

5 7 4 0
rain 1 3 3 5
mild
sun 2 1 7 4 
rain 3 1 5 3

Sample Output

17 4

Note

Ảnh phía trên mô tả trạng thái khu vườn của bác nông dân trong ví dụ sau $4$ ngày. Khu vườn xuất hiện $4$ vùng đất với tổng cộng $17$ ô đất có thể trồng trọt (các ô đất có độ ẩm là $0$).