User Journey Paths

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem.

Problem

User Journey Paths (Action Log Trie Summary)

You are given action logs emitted by a platform. Each log entry is a tuple: (user_id, time, action).

Build a path tree (Trie-like summary) of users’ journeys:

For each user, sort their logs by time ascending to obtain that user’s action sequence.

Insert each user’s sequence into a tree.

Each node represents an action; a path from the root represents an action-prefix.

Each node stores a count = the number of distinct users whose journey reached that node via that prefix.

Input

List[Tuple[int, int, str]] log entries (user_id, time, action).

Output

Return an indented string representation of the tree:

Do not print the root.

Each line: ACTION (count).

Children are indented by two spaces and prefixed with -> .

For deterministic output, print siblings in lexicographic order by action.

Notes / Edge cases

Logs can be unordered: group by user and sort by time.

Each user contributes +1 to every prefix node along their path.

Repeated actions are distinct steps (e.g., A -> B -> B is valid; the second B is a child of the first B).

Empty input ⇒ empty output string.

Single user / single action ⇒ single node.

Example

Input logs:

100 1000 A

300 1150 A

200 1200 B

100 1200 B

100 1300 C

200 1400 A

300 1500 B

300 1550 B

100 1560 D

Per-user sequences:

user 100: A -> B -> C -> D

user 200: B -> A

user 300: A -> B -> B

Expected output:

A (2)

-> B (2)

-> B (1)

-> C (1)

-> D (1)

B (1)

-> A (1)

Tests

Use the 5 test cases described in the prompt (main example, empty, single action, identical paths, out-of-order logs).

Example

Input

100 1000 A

300 1150 A

200 1200 B

100 1200 B

100 1300 C

200 1400 A

300 1500 B

300 1550 B

100 1560 D

Output

A (2)

-> B (2)

-> B (1)

-> C (1)

-> D (1)

B (1)

-> A (1)

Complete solveUserJourneyPaths. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.