Chef has a rectangular piece of paper. He puts it on a big board in such a way that two sides of the paper are horizontal and two are vertical, and then he performs a sequence of $N$ operations. You are given a string $S$ with length $N$; for each valid $i$, the $i$-th character of $S$ determines the type of the $i$-th operation:
- 'R': Pick up the paper from the right side and fold it onto the left side.
- 'L': Pick up the paper from the left side and fold it onto the right side.
- 'U': Pick up the paper from the upper side and fold it onto the bottom side.
- 'D': Pick up the paper from the bottom side and fold it onto the upper side.
The paper is folded in such a way that there is still a flat rectangular sheet of paper lying on the table after each operation, but it consists of multiple layers of the original sheet. The lengths of the horizontal and vertical sides of the resulting sheet (after performing these $N$ operations) are $W$ and $H$ respectively. Let's build an Euclidean coordinate system on the paper, where the point $(0, 0)$ corresponds to the bottom left corner and $(W, H)$ to the upper right corner.
Chef then draws $M$ points on this folded sheet of paper. The ink used to draw them soaks deep into the paper, so each point is drawn on all layers of the paper (and also on both faces of each layer). 
Finally, Chef completely unfolds the paper. He's asking you to compute the distance between the nearest pair of points.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains four space-separated integers $N$, $M$, $W$ and $H$.
- The second line contains a single string $S$.
- Each of the following $M$ lines contains two space-separated integers $X$ and $Y$ denoting the coordinates of one point.

-----Output-----
For each test case, print a single line containing one real number ― the minimum distance. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$.

-----Constraints-----
- $1 \le T \le 50$
- $2 \le M \le 1,000$
- $1 \le N \le 1,000$
- $3 \le W, H \le 10^9$
- $1 \le X \le W-1$
- $1 \le Y \le H-1$
- the points are pairwise distinct

-----Subtasks-----
Subtask #1 (50 points): all characters of $S$ are 'U'
Subtask #2 (50 points): original constraints

-----Example Input-----
2
6 2 10 10
ULRDDL
4 4
5 5
4 2 10 10
RUDL
1 1
9 9

-----Example Output-----
1.41421356237
2.00000000000

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "# cook your dish here folding paper\nfrom collections import Counter\ndef li():return [int(i) for i in input().rstrip('\\n').split()]\ndef st():return input().rstrip('\\n')\ndef val():return int(input().rstrip('\\n'))\ndef dist(a,b):return ((a[0]-b[0])**2+(a[1]-b[1])**2)**0.5\nfor _ in range(val()):\n n,m,w,h=li()\n s=Counter(st())\n l=[]\n for i in range(m):\n  l.append(li())\n ans=float('inf')\n l.sort(key=lambda x:x[0])\n for j in range(1,50):\n  for i in range(j,m):\n   ans=min(ans,dist(l[i-j],l[i]))\n for i in l:\n  if s['D'] or s['U']>1:ans=min(ans,2*i[1])\n  if s['U'] or s['D']>1:ans=min(ans,2*(h-i[1]))\n  if s['L'] or s['R']>1:ans=min(ans,2*i[0])\n  if s['R'] or s['L']>1:ans=min(ans,2*(w-i[0]))\n print(ans)"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14991