Sarah is experimenting with a new video meeting service called Dash, but unfortunately has a poor internet connection. She wants to optimize her Dash experience by finding the point in her house with the best internet connection from a small set of landmarks. You must create a program that finds the quickest route that visits all of these landmarks, so that Sarah can decide where to take her Dash meetings as quickly as possible.
Sarah's house can be represented by a 2D grid with impassable walls and markings for her current location and the location of each landmark. Given this 2D grid, find the length of the minimum path that starts from Sarah's location and visits all of the landmarks in her house. Sarah can move in any of the cardinal directions throughout this grid, but can't leave the grid or go through walls.
You are guaranteed that all the landmarks are reachable from Sarah's current location.
The first line of the input contains three integers $n$, $m$, and $k$ ($1 <= n, m <= 500 \; 1 <= k <= 6$) – the number of rows, the number of columns, and the number of landmarks in the grid representation of Sarah's house. The next $n$ lines consist of $m$ characters that are either _S_ to denote Sarah's starting position, _X_ to denote a landmark, _*_ to denote an impassable wall, and _._ to denote an empty space in the grid.
Print one integer – the length of the minimum path that starts from Sarah's location and visits all of the landmarks in her house.
## Input
The first line of the input contains three integers $n$, $m$, and $k$ ($1 <= n, m <= 500 \; 1 <= k <= 6$) – the number of rows, the number of columns, and the number of landmarks in the grid representation of Sarah's house. The next $n$ lines consist of $m$ characters that are either _S_ to denote Sarah's starting position, _X_ to denote a landmark, _*_ to denote an impassable wall, and _._ to denote an empty space in the grid.
## Output
Print one integer – the length of the minimum path that starts from Sarah's location and visits all of the landmarks in her house.
[samples]
**Definitions**
Let $ n, m, k \in \mathbb{Z}^+ $ denote the grid dimensions and number of landmarks, with $ 1 \leq n, m \leq 500 $, $ 1 \leq k \leq 6 $.
Let $ G $ be an $ n \times m $ grid with cells labeled as:
- $ S $: unique starting position,
- $ X $: landmark positions (exactly $ k $ of them),
- $ * $: impassable walls,
- $ . $: passable empty space.
Let $ P_0 \in \mathbb{Z}^2 $ be the coordinates of $ S $, and $ P_1, \dots, P_k \in \mathbb{Z}^2 $ be the coordinates of the $ k $ landmarks.
Let $ d(p, q) $ denote the shortest Manhattan-path distance (number of cardinal steps) between two passable grid points $ p $ and $ q $, avoiding walls.
**Constraints**
1. All landmarks and $ S $ are reachable from each other via passable cells.
2. Grid boundaries are respected; no movement outside $ [0, n-1] \times [0, m-1] $.
**Objective**
Find the minimum length of a path starting at $ P_0 $ that visits all $ k $ landmarks in some order:
$$
\min_{\sigma \in S_k} \left( \sum_{i=0}^{k-1} d(P_{\sigma(i)}, P_{\sigma(i+1)}) \right)
$$
where $ \sigma $ is a permutation of $ \{1, 2, \dots, k\} $, and $ \sigma(0) = 0 $ (fixed start at $ S $).