Cho một xẫu kí tự S bao gồm các chữ cái và dấu cách (một từ được định nghĩa là các kí tự liên tiếp không chứa dấu cách), hãy đếm xem mỗi từ trong xâu xuất hiện bao nhiêu lần, đầu tiên hãy liệt kê các từ trong xâu kèm theo tần suất của mỗi từ theo thứ tự từ điển, sau đó liệt kê các từ trong xâu theo thứ tự xuất hiện.

Ràng buộc: ~1 \leq len(s) \leq 100000~

Đầu ra: Đầu tiên in ra các từ trong xâu và tần suất của nó theo thứ tự từ điển. Sau đó bỏ trống 1 dòng và in ra các từ trong xâu và tần suất của nó theo thứ tự xuất hiện trong xâu.

Input:

bb aa bb cc aa bb cc

Output:

aa 2
bb 3
cc 2

bb 3
aa 2
cc 2