Word frequency report

Problem

Given a line of words, report how many times each different word appears.

Print one line per word as word count, in the order the words first appear.

Input: One line with words separated by spaces.
Output: For each different word, in order of first appearance, one line: the word, a space, and its count.
Constraints: 1 ≤ number of words ≤ 10000

Example

Input

north south north east south north

Output

north 3
south 2
east 1

North appears three times, south twice, east once.

Try the problem first. Open one hint at a time.

Hint 1

Count with a dictionary. Dictionaries remember the order in which keys were added.

Hint 2

After counting, loop over counts.items() and print each pair.

Write your Python code, run it on the examples and submit it to hidden tests.