Cho một hình vuông có cạnh bằng 3, biết mỗi cạnh hình vuông được ghép từ 3 số trong khoảng [1..8]

VD:

1 2 3

8 _ 4

7 6 5

Bạn được cho biết một số ở góc trái bên cùng

1 ? ?

? _ ?

? ? ?

Hỏi có bao nhiêu cách xắp xếp các số còn lại vào cạnh hình vuông sao cho tổng mỗi cạnh bằng 12

Sample Input 1

8

Sample Output 1

0

Sample Input 2

6

Sample Output 2

2

Một ngày nó admin page này bày tỏ sự bận bịu của mình với hiện nhân phương tây và nội dung cuộc hội thoại như sau:

tôi đi crawl đề đây 

crawl đề cũng mất time lắm á 

chọn contest => crawl => upload đề => submit thử từng câu => tạo contest 

đấy thấy bận bịu chưa

Vì thấy admin n giấu tên quá bận rộn nên hiền nhân phương tây đã cho anh một chuyến du lịch vào thế giới 2D để giải tỏa sau chuỗi ngày căng thẳng. Ở thế giới này có N cổng dịch chuyển có tọa độ là (x, y) biết rằng từ cổng này bạn có thể dịch chuyển đến một cổng bất kì. Vì còn quá trời dealine nên admin đang cố gắng đi ra khỏi thế giới này càng sớm càng tốt nhưng do code quá nhiều nên anh ấy không còn đi như người bth mà chỉ có thể đi theo hướng (x+d, y) (d≥1).

Nhằm giúp admin n giấu tên ở lại thế giới lâu hơn nên ngài quyết định kết nối các cặp cổng dịch chuyển sao cho tạo thành một chuỗi lặp vô tận.

VD: ta có 2 cổng A(1,1) B(3,1) kết nối với nhau và admin xuất phát ở tọa độ (2,1). Admin di chuyển theo hướng (x+d, y) (d≥1) nên bước tiếp theo anh ta sẽ đến B(3,1). cổng B kết nối với cổng A nên sẽ dịch chuyển đến A(1,1) và sau đó admin bận bịu lại đi tiếp thế là anh ta bị mắc vào một vòng lặp vô tận.

*Chú ý: 2 cổng A và B kết nối thì ta có thể đi từ A đến B và ngược lại từ B đến A Nhằm tạo một thế giới đẹp nhất có thể hiền nhân hỏi bạn có bao nhiêu cách ghép các cặp cổng để admin vĩnh viễn ở lại

2≤N ≤12

0≤x, y≤1e9

Sample Input 1

4
0 0
1 0
1 1
0 1

Sample Output 1

2

Ta đánh số các đỉnh lần lượt từ 1..4 Từ đó ta có các cách ghép như sau để admin bận bịu mãi mãi bận bịu

.1→3 và 2→4

.1→2và 3->4

Bạn có một xâu S gồm các chữ cái viết thường độ dài N và một xâu T có độ dài là M cũng chỉ bao gồm các chữ cái viết thường. Nhiệm vụ của bạn là xóa xâu T khỏi S bằng phương pháp sau:

• Khi vừa phát hiện sâu T trong sâu S bạn sẽ lặp tức xóa nó đi và lặp lại thao tác này cho đến khi không còn xâu T trong S nữa. Lưu ý việc xóa đi sâu T sẽ có thể dẫn đến hình thành xâu T mới trong S

Xuất ra sâu cuối sau khi thực hiện phương pháp trên Đảm bảo kết quả còn lại sẽ không có xâu trống nào

1≤N≤1e6

1≤M≤100

Sample Input 1

daihooccongnghiep
oc

Sample Output 1

daihongnghiep

Sample Input 2

cacarrcara
car

Sample Output 2

a

Tết là một dịp lễ ai cũng mong chờ để được nghỉ ngơi, xum vầy bên gia đình sau một năm làm việc và học tập. Và thứ mà các bạn sinh viên của thầy Luna đều muốn nhận được là lì xì Tết. Thầy Luna có số tiền ban đầu là s và có n sinh viên, mỗi sinh viên thứ i (1 ≤ i ≤ n) sẽ lần lượt đến nhà thầy.

• Nếu sinh viên đến lì xì cho thầy số tiền là x thì thầy sẽ nhận hết (nói cách khác s = s + x).
• Nếu sinh viên đến xin lì xì từ thầy thì sẽ hi vọng nhận được số tiền là x. Thầy sẽ lì xì cho sinh viên đó nếu x ≤ s (với s là số tiền hiện tại thầy đang có) và số tiền của thầy sẽ giảm đi x (hay s = s - x). Ngược lại thì số tiền của thầy Luna sẽ giữ nguyên và sinh viên đó sẽ khóc và bỏ đi.

Thầy Luna muốn biết rằng sau khi Tết đi qua thì số tiền còn lại và số học sinh đã buồn và bỏ đi là bao nhiêu.

Input

Dòng dầu tiên chứa 2 số nguyên n và x (1 <= n, ~s<=10^5~)

Tiếp theo là n dòng, dòng thứ i (1 ≤ i ≤ n) sẽ chứa ký tự c và một số nguyên x (~1 <= x <=10^9 ~) biểu thị nếu c = '+' thì sinh viên đó đến lì xì cho thầy. Ngược lại nếu c = '-' thì sinh viên đó đến xin lì xì từ thầy .

Output

Một dòng duy nhất chứa hai số nguyên là số tiền còn lại và số học sinh đã buồn bã bỏ đi.

Examples

Input

5 100 
+ 200 
- 50 
- 150
+ 20  
- 200 

Output

120 1 

Bạn có ba xô nước có thể tích lần lược là A, B, C ban đầu xô A và B không có nước, xô C đầy nước. Biết admin IUHcoder là một người lười biếng nhưng hôm nay anh ấy siêng lạ thường nên anh tự đặt ra một câu hỏi cho bản thân và nội dung câu hỏi như sau:

• Số lượng thể tích khác nhau có thể còn lại trong xô C khi anh ấy đổ nước từ xô này sang xô khác?
• Biết rằng trong quá trình đổ nước từ xô này sang xô khác sẽ dừng lại khi xô dùng để đổ nước không còn nước hoặc xô dùng để đựng nước đầy.

Tuy tự mình đặt ra câu hỏi nhưng lại là một admin lười biếng nên anh quyết định để câu hỏi này lại cho bạn. Nhiêm vụ của bạn là in ra danh sách các thể tích khác nhau có thể khi thực hiện quá trình trên theo thứ tự tăng dần.

1<= A, B, C <=20

Sample Input 1

8 9 10

Sample Output 1

0 1 2 8 9 10

Sample Input 2

2 5 10

Sample Output 2

3 4 5 6 7 8 9 10

Vì nóc nhà H giấu tên của admin N giấu tên gọi admin đi gánh nước và trong sự bận bịu và cay cú nên anh đã không kịp giải thích test đề =))

Giải thích test 1: Lượng nước ban đầu trong 3 xô lần lượt là: 0, 0, 10

• Xô C còn lại 1 lít khi đổ xô C qua xô B, khi đó lượng nước trong 3 xô lần lượt là 0, 9, 1
• Xô C còn lại 2 lít khi đổ xô C qua xô A, khi đó lượng nước trong 3 xô lần lượt là 8, 0, 2
• Xô C còn lại 0 và 8 lít khi đổ nước 3 lần. Lần thứ nhất đổ xô C qua xô A, khi đó lượng nước trong 3 xô lần lượt là 8, 0, 2. Lần thứ hai đổ xô C qua xô B, khi đó lượng nước trong 3 xô lần lượt là 8, 2, 0 (lúc này xô C có lượng nước là 0). Lần thứ 3 đổ xô A qua xô C, khi đó lượng nước trong 3 xô lần lượt là 0, 2, 8 (lúc này xô C có lượng nước là 8).