Hiếu mới lắp ráp một robot có thể di chuyển trên trục số.
Robot của Hiếu thực hiện các thao tác di chuyển dựa trên một dãy lệnh \(S=s_1s_2\dots s_n\) \((s_i \in \{\texttt{L, R}\})\).

Nếu robot đang đứng ở vị trí \(x\) trên trục số và di chuyển theo lệnh \(s\) thì robot sẽ thực hiện như sau:

• Nếu \(s_i=\texttt{L}\) thì robot di chuyển sang bên trái trục số 1 đơn vị, hay là \(x \leftarrow x-1\)
• Nếu \(s_i=\texttt{R}\) thì robot di chuyển sang bên phải trục số 1 đơn vị, hay là \(x \leftarrow x+1\)

Ban đầu, robot đứng ở vị trí \(x_0\). Hiếu lập trình robot lần lượt thực hiện việc di chuyển trong \(k\) lượt dựa theo dãy lệnh \(s\):

• Lượt đầu tiên thực hiện lệnh \(1\)
• Nếu lượt trước đó thực hiện lệnh thứ \(i\), thì lượt tiếp theo thực hiện lệnh thứ \((i\ \text{mod}\ n) + 1\)

Để làm được việc này, robot có một ô nhớ chứa chỉ số của lệnh vừa thực hiện trước đó. Nếu sau khi thực hiện một lệnh \(s_i\), ô nhớ này cần chứa giá trị \(i\).

Tuy nhiên, do sự không cẩn thận của mình, Hiếu lại có một lỗi bộ nhớ. Nếu sau khi thực hiện một lệnh \(s_i\) mà robot trở về vị trí \(0\) thì ô nhớ chứa thứ tự lệnh trước đó thực hiện bị gán lại về giá trị \(0\) thay vì chứa giá trị \(i\) (lệnh tiếp theo sẽ là lệnh thứ \(1\)).

Tuy có lỗi bộ nhớ, robot vẫn thực hiện \(k\) lượt. Bạn hãy trả lời hai câu hỏi sau:

1. Robot đến điểm \(0\) tổng cộng bao nhiêu lần?
2. Sau \(k\) lượt, robot đang đứng tại điểm nào?

Input

• Dòng đầu tiên chứa số \(t\) (\(1 \leq t \leq 10\)) -- là số lượng test
• Tiếp theo là \(t\) test, mỗi test được ghi trên 2 dòng theo định dạng:
  • Dòng thứ nhất chứa ba số nguyên \(n, x_0, k\) \((1 \leq n \leq 10^5; 1 \leq |x_0| \leq 10^{18}; 1 \leq k \leq 10^{18})\)
  • Dòng thứ hai gồm duy nhất một xâu \(S\). Dữ liệu đảm bảo độ dài xâu \(S\) là \(n\)

Output

• In ra \(t\) dòng ứng với \(t\) test, mỗi dòng chứa hai số lần lượt là:
  • Số lần mà robot đến tọa độ \(0\)
  • Tọa độ mà robot đang đứng sau \(k\) lượt

Scoring

• Subtask \(1\) (\(35\%\) số điểm): \(k \leq 10^6\)
• Subtask \(2\) (\(20\%\) số điểm): \(s_i = s_1, \forall i\)
• Subtask \(3\) (\(15\%\) số điểm): \(|x| \leq n\)
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc nào thêm

Example

6
3 2 6
LLR
2 -1 8
RL
4 -2 5
LRRR
5 3 7
LRRLL
1 1 1
L
3 -1 4846549234412827
RLR

1 -2
4 1
1 -1
0 2
1 0
2423274617206414 0