问题

### Instructions: You are an expert Python programmer. You will be given a question (problem specification) and will generate a correct Python program that matches the specification and passes all tests. You will NOT return anything except for the program.
### Question:
Takahashi has created a game where the player controls a dragon on a coordinate plane.
The dragon consists of N parts numbered 1 to N, with part 1 being called the head.
Initially, part i is located at the coordinates (i,0). Process Q queries as follows.

- 1 C: Move the head by 1 in direction C. Here, C is one of R, L, U, and D, which represent the positive x-direction, negative x-direction, positive y-direction, and negative y-direction, respectively. Each part other than the head moves to follow the part in front of it. That is, part i (2\leq i \leq N) moves to the coordinates where part i-1 was before the move.
- 2 p: Find the coordinates of part p.

Input

The input is given from Standard Input in the following format:
N Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

Each query is in one of the following two formats:
1 C

2 p

Output

Print q lines, where q is the number of queries of the second type.
The i-th line should contain x and y separated by a space, where (x,y) are the answer to the i-th such query.

Constraints


- 2 \leq N \leq 10^6
- 1 \leq Q \leq 2\times 10^5
- For the first type of query, C is one of R, L, U, and D.
- For the second type of query, 1\leq p \leq N.
- All numerical input values are integers.

Sample Input 1

5 9
2 3
1 U
2 3
1 R
1 D
2 3
1 L
2 1
2 5

Sample Output 1

3 0
2 0
1 1
1 0
1 0

At each time when processing the second type of query, the parts are at the following positions:

Note that multiple parts may exist at the same coordinates.

### Format: Read the inputs from stdin solve the problem and write the answer to stdout (do not directly test on the sample inputs). Enclose your code within delimiters as follows.
```python
# YOUR CODE HERE
```

### Answer: (use the provided format with backticks)

答案

模型 模型答案 正确答案
金声玉亮2.0 ```python
import sys
input = sys.stdin.read
data = input().split()

N = int(data[0])
Q = int(data[1])

queries = data[2:]

# Initial positions of the dragon parts
positions = [[i, 0] for i in range(1, N+1)]

# Direction vectors
directions = {
'R': (1, 0),
'L': (-1, 0),
'U': (0, 1),
'D': (0, -1)
}

# Process queries
index = 0
for i in range(Q):
query_type = int(queries[index])
if query_type == 1:
direction = queries[index + 1]
dx, dy = directions[direction]
# Move the head
positions[0][0] += dx
positions[0][1] += dy
# Move the rest of the parts
for j in range(1, N):
positions[j][0] = positions[j-1][0] - dx
positions[j][1] = positions[j-1][1] - dy
index += 2
elif query_type == 2:
part = int(queries[index + 1])
print(positions[part-1][0], positions[part-1][1])
index += 2
```		 [{"input": "5 9\n2 3\n1 U\n2 3\n1 R\n1 D\n2 3\n1 L\n2 1\n2 5\n", "output": "3 0\n2 0\n1 1\n1 0\n1 0\n", "testtype": "stdin"}]
deepseek-r1

```python
def main():
import sys
input = sys.stdin.read
data = input().split()
idx = 0
N = int(data[idx])
idx += 1
Q = int(data[idx])
idx += 1

head_history = [(1, 0)]

results = []

for _ in range(Q):
if data[idx] == '1':
C = data[idx + 1]
idx += 2
dx, dy = 0, 0
if C == 'R':
dx = 1
elif C == 'L':
dx = -1
elif C == 'U':
dy = 1
elif C == 'D':
dy = -1
current_x, current_y = head_history[-1]
new_x = current_x + dx
new_y = current_y + dy
head_history.append((new_x, new_y))
else:
p = int(data[idx + 1])
idx += 2
m = len(head_history) - 1
if m >= (p - 1):
s = m - (p - 1)
x, y = head_history[s]
else:
x = p - m
y = 0
results.append(f"{x} {y}")

print('\n'.join(results))

if __name__ == "__main__":
main()
```		 [{"input": "5 9\n2 3\n1 U\n2 3\n1 R\n1 D\n2 3\n1 L\n2 1\n2 5\n", "output": "3 0\n2 0\n1 1\n1 0\n1 0\n", "testtype": "stdin"}]
gpto1 ```python
# YOUR CODE HERE
import sys
import threading
def main():
import sys
sys.setrecursionlimit(1 << 25)
N, Q = map(int, sys.stdin.readline().split())
total_moves = 0
sdx = [0]
sdy = [0]
moves = []
queries = []
for _ in range(Q):
s = sys.stdin.readline().strip()
if s[0] == '1':
# Type 1 query
_, C = s.split()
if C == 'R':
dx, dy = 1, 0
elif C == 'L':
dx, dy = -1, 0
elif C == 'U':
dx, dy = 0, 1
elif C == 'D':
dx, dy = 0, -1
else:
dx, dy = 0, 0
sdx.append(sdx[-1] + dx)
sdy.append(sdy[-1] + dy)
total_moves +=1
else:
# Type 2 query
_, p = s.split()
p = int(p)
m_p = max(0, total_moves - (p -1))
m_p_start = total_moves - m_p
dx = sdx[total_moves] - sdx[m_p_start]
dy = sdy[total_moves] - sdy[m_p_start]
x_p = p + dx
y_p = 0 + dy
print(int(x_p), int(y_p))
threading.Thread(target=main,).start()
```		 [{"input": "5 9\n2 3\n1 U\n2 3\n1 R\n1 D\n2 3\n1 L\n2 1\n2 5\n", "output": "3 0\n2 0\n1 1\n1 0\n1 0\n", "testtype": "stdin"}]
gpt-4o-2024-08-06 ```python
# YOUR CODE HERE
import sys
input = sys.stdin.read

def main():
data = input().split()
N = int(data[0])
Q = int(data[1])

# Initial positions of the dragon parts
positions = [(i, 0) for i in range(1, N + 1)]

# Direction vectors
direction_map = {
'R': (1, 0),
'L': (-1, 0),
'U': (0, 1),
'D': (0, -1)
}

index = 2
results = []

for _ in range(Q):
query_type = int(data[index])

if query_type == 1:
# Move the head
C = data[index + 1]
dx, dy = direction_map[C]

# Move the head
new_head_position = (positions[0][0] + dx, positions[0][1] + dy)

# Move each part to the position of the part in front of it
for i in range(N - 1, 0, -1):
positions[i] = positions[i - 1]

# Update the head position
positions[0] = new_head_position

index += 2

elif query_type == 2:
# Query the position of part p
p = int(data[index + 1])
x, y = positions[p - 1]
results.append(f"{x} {y}")

index += 2

# Print all results for type 2 queries
print("\n".join(results))

main()
```		 [{"input": "5 9\n2 3\n1 U\n2 3\n1 R\n1 D\n2 3\n1 L\n2 1\n2 5\n", "output": "3 0\n2 0\n1 1\n1 0\n1 0\n", "testtype": "stdin"}]
DeepSeek-Coder-V2-Lite-Instruct ```python
# YOUR CODE HERE

def main():
import sys
input = sys.stdin.read
data = input().split()

index = 0
N = int(data[index])
Q = int(data[index + 1])
index += 2

# Initialize the positions of the parts
positions = [(i, 0) for i in range(1, N + 1)]

# Process the queries
for _ in range(Q):
query_type = int(data[index])
index += 1

if query_type == 1:
direction = data[index]
index += 1

# Move the head
head_x, head_y = positions[0]
if direction == 'R':
positions[0] = (head_x + 1, 0)
elif direction == 'L':
positions[0] = (head_x - 1, 0)
elif direction == 'U':
positions[0] = (head_x, head_y + 1)
elif direction == 'D':
positions[0] = (head_x, head_y - 1)

# Move the rest of the parts
for i in range(1, N):
positions[i] = positions[i - 1]

elif query_type == 2:
part_index = int(data[index])
index += 1

# Output the coordinates of the specified part
print(positions[part_index - 1][0], positions[part_index - 1][1])

if __name__ == "__main__":
main()
```		 [{"input": "5 9\n2 3\n1 U\n2 3\n1 R\n1 D\n2 3\n1 L\n2 1\n2 5\n", "output": "3 0\n2 0\n1 1\n1 0\n1 0\n", "testtype": "stdin"}]
Meta-Llama-3.1-405B-Instruct-Turbo ```python
import sys

def main():
n, q = map(int, sys.stdin.readline().split())
x, y = [0] * (n + 1), [0] * (n + 1)
for i in range(1, n + 1):
x[i] = i

dx = {'R': 1, 'L': -1, 'U': 0, 'D': 0}
dy = {'R': 0, 'L': 0, 'U': 1, 'D': -1}
head_x, head_y = 1, 0
tail_x, tail_y = n, 0
for _ in range(q):
query = sys.stdin.readline().split()
if query[0] == '1':
direction = query[1]
new_head_x, new_head_y = head_x + dx[direction], head_y + dy[direction]
x[1], y[1] = new_head_x, new_head_y
head_x, head_y = new_head_x, new_head_y
for i in range(2, n + 1):
new_x, new_y = x[i - 1], y[i - 1]
old_x, old_y = x[i], y[i]
x[i], y[i] = new_x, new_y
if i == n:
tail_x, tail_y = old_x, old_y
else:
p = int(query[1])
if p == n:
print(tail_x, tail_y)
else:
print(x[p], y[p])

if __name__ == '__main__':
main()
```		 [{"input": "5 9\n2 3\n1 U\n2 3\n1 R\n1 D\n2 3\n1 L\n2 1\n2 5\n", "output": "3 0\n2 0\n1 1\n1 0\n1 0\n", "testtype": "stdin"}]
Meta-Llama-3.1-70B-Instruct-Turbo ```python
import sys

N, Q = map(int, sys.stdin.readline().split())
queries = [sys.stdin.readline().split() for _ in range(Q)]

dx = {'R': 1, 'L': -1, 'U': 0, 'D': 0}
dy = {'R': 0, 'L': 0, 'U': 1, 'D': -1}

x, y = 1, 0
moves = [(0, 0)]
for query in queries:
if query[0] == '1':
c = query[1]
x += dx[c]
y += dy[c]
moves.append((x, y))
else:
p = int(query[1])
if p == 1:
print(x, y)
else:
if p < len(moves):
print(moves[p][0], moves[p][1])
else:
print(moves[-1][0] + (p - len(moves)) * dx['R'], moves[-1][1] + (p - len(moves)) * dy['R'])
```		 [{"input": "5 9\n2 3\n1 U\n2 3\n1 R\n1 D\n2 3\n1 L\n2 1\n2 5\n", "output": "3 0\n2 0\n1 1\n1 0\n1 0\n", "testtype": "stdin"}]
Qwen2-72B-Instruct ```python
from collections import deque

N, Q = map(int, input().split())
dragon = deque([(i, 0) for i in range(N)])

ans = []
for _ in range(Q):
query = list(map(str, input().split()))
if query[0] == "1":
head_x, head_y = dragon[0]
if query[1] == "R":
dragon.appendleft((head_x + 1, head_y))
elif query[1] == "L":
dragon.appendleft((head_x - 1, head_y))
elif query[1] == "U":
dragon.appendleft((head_x, head_y + 1))
else:
dragon.appendleft((head_x, head_y - 1))
dragon.pop()
else:
ans.append(dragon[int(query[1]) - 1])

for a in ans:
print(a[0], a[1])
```
```		 [{"input": "5 9\n2 3\n1 U\n2 3\n1 R\n1 D\n2 3\n1 L\n2 1\n2 5\n", "output": "3 0\n2 0\n1 1\n1 0\n1 0\n", "testtype": "stdin"}]
baichuan4 ```python
import sys

# Read input values
N, Q = map(int, sys.stdin.readline().split())
dragon_parts = [(i, 0) for i in range(1, N+1)]

# Function to move the dragon's head
def move_head(direction):
global dragon_parts
head_x, head_y = dragon_parts[0]
if direction == 'R':
head_x += 1
elif direction == 'L':
head_x -= 1
elif direction == 'U':
head_y += 1
elif direction == 'D':
head_y -= 1
dragon_parts = [(head_x, head_y)] + dragon_parts[1:]

# Function to get the position of a part
def get_part_position(p):
return dragon_parts[p-1]

# Process queries
for _ in range(Q):
query = sys.stdin.readline().strip().split()
if query[0] == '1':
move_head(query[1])
elif query[0] == '2':
part_position = get_part_position(int(query[1]))
print(f"{part_position[0]} {part_position[1]}")
```
```		 [{"input": "5 9\n2 3\n1 U\n2 3\n1 R\n1 D\n2 3\n1 L\n2 1\n2 5\n", "output": "3 0\n2 0\n1 1\n1 0\n1 0\n", "testtype": "stdin"}]
doubao ```python
import sys

N, Q = map(int, sys.stdin.readline().split())
parts = [(i, 0) for i in range(1, N + 1)]

for _ in range(Q):
query = sys.stdin.readline().split()
if query[0] == '1':
direction = query[1]
if direction == 'U':
parts[0] = (parts[0][0], parts[0][1] + 1)
elif direction == 'D':
parts[0] = (parts[0][0], parts[0][1] - 1)
elif direction == 'R':
parts[0] = (parts[0][0] + 1, parts[0][1])
elif direction == 'L':
parts[0] = (parts[0][0] - 1, parts[0][1])
for i in range(1, N):
parts[i] = parts[i - 1]
elif query[0] == '2':
p = int(query[1])
print(*parts[p - 1])
```		 [{"input": "5 9\n2 3\n1 U\n2 3\n1 R\n1 D\n2 3\n1 L\n2 1\n2 5\n", "output": "3 0\n2 0\n1 1\n1 0\n1 0\n", "testtype": "stdin"}]
gpto1 ```python
# YOUR CODE HERE
import sys
import threading
def main():
import sys
sys.setrecursionlimit(1 << 25)
N, Q = map(int, sys.stdin.readline().split())
total_moves = 0
sdx = [0]
sdy = [0]
moves = []
queries = []
for _ in range(Q):
s = sys.stdin.readline().strip()
if s[0] == '1':
# Type 1 query
_, C = s.split()
if C == 'R':
dx, dy = 1, 0
elif C == 'L':
dx, dy = -1, 0
elif C == 'U':
dx, dy = 0, 1
elif C == 'D':
dx, dy = 0, -1
else:
dx, dy = 0, 0
sdx.append(sdx[-1] + dx)
sdy.append(sdy[-1] + dy)
total_moves +=1
else:
# Type 2 query
_, p = s.split()
p = int(p)
m_p = max(0, total_moves - (p -1))
m_p_start = total_moves - m_p
dx = sdx[total_moves] - sdx[m_p_start]
dy = sdy[total_moves] - sdy[m_p_start]
x_p = p + dx
y_p = 0 + dy
print(int(x_p), int(y_p))
threading.Thread(target=main,).start()
```		 [{"input": "5 9\n2 3\n1 U\n2 3\n1 R\n1 D\n2 3\n1 L\n2 1\n2 5\n", "output": "3 0\n2 0\n1 1\n1 0\n1 0\n", "testtype": "stdin"}]
kimi ```python
(N, Q) = map(int, input().split())
pos = [0] * N
dir = [0, 1]
for _ in range(Q):
query = input().split()
if query[0] == '1':
C = query[1]
if C == 'R':
pos[0] += 1
elif C == 'L':
pos[0] -= 1
elif C == 'U':
dir[1] += 1
elif C == 'D':
dir[1] -= 1
for i in range(1, N):
pos[i] = pos[i - 1] + dir[0]
dir[0] = dir[1]
else:
p = int(query[1]) - 1
print(pos[p], dir[1] * p)
```		 [{"input": "5 9\n2 3\n1 U\n2 3\n1 R\n1 D\n2 3\n1 L\n2 1\n2 5\n", "output": "3 0\n2 0\n1 1\n1 0\n1 0\n", "testtype": "stdin"}]
minimax ```python
# YOUR CODE HERE
N, Q = map(int, input().split())
queries = [input().split() for _ in range(Q)]

# Initialize the positions of the dragon parts
positions = [(i, 0) for i in range(1, N + 1)]

# Process the queries
for query in queries:
if query[0] == '1':
# Move the head
direction = query[1]
head_pos = positions[0]
if direction == 'R':
new_head_pos = (head_pos[0] + 1, head_pos[1])
elif direction == 'L':
new_head_pos = (head_pos[0] - 1, head_pos[1])
elif direction == 'U':
new_head_pos = (head_pos[0], head_pos[1] + 1)
elif direction == 'D':
new_head_pos = (head_pos[0], head_pos[1] - 1)

# Update positions of all parts
positions = [new_head_pos] + [(positions[i][0] - positions[i-1][0] + new_head_pos[0], positions[i][1] - positions		 [{"input": "5 9\n2 3\n1 U\n2 3\n1 R\n1 D\n2 3\n1 L\n2 1\n2 5\n", "output": "3 0\n2 0\n1 1\n1 0\n1 0\n", "testtype": "stdin"}]
wenxinyiyan ```python
from sys import stdin

# Initialize the dragon's parts positions
def initialize_positions(N):
return [(i, 0) for i in range(1, N + 1)]

# Move the dragon's head and update the positions of other parts
def move_dragon(positions, direction):
head_x, head_y = positions[0]
if direction == 'R':
new_head_x = head_x + 1
new_head_y = head_y
elif direction == 'L':
new_head_x = head_x - 1
new_head_y = head_y
elif direction == 'U':
new_head_x = head_x
new_head_y = head_y + 1
elif direction == 'D':
new_head_x = head_x
new_head_y = head_y - 1

# Update the positions
new_positions = [positions[0]] # Head doesn't move yet
for i in range(1, len(positions)):
new_positions.append(positions[i-1]) # Each part moves to the previous part's position

# Now move the head
new_positions[0] = (new_head_x, new_head_y)
return new_positions

# Main program
N, Q = map(int, stdin.readline().split())
positions = initialize_positions(N)

for _ in range(Q):
query = stdin.readline().strip()
if query[0] == '1':
direction = query[2]
positions = move_dragon(positions, direction)
elif query[0] == '2':
p = int(query[2:])
x, y = positions[p-1]
print(f"{x} {y}")
```		 [{"input": "5 9\n2 3\n1 U\n2 3\n1 R\n1 D\n2 3\n1 L\n2 1\n2 5\n", "output": "3 0\n2 0\n1 1\n1 0\n1 0\n", "testtype": "stdin"}]
zhipu ```python
import sys
input = sys.stdin.read

def main():
data = input().split()
N = int(data[0])
Q = int(data[1])

queries = data[2:]

# Initial positions of the parts
x = list(range(1, N + 1))
y = [0] * N

# Direction mappings
direction_map = {
'R': (1, 0),
'L': (-1, 0),
'U': (0, 1),
'D': (0, -1)
}

output = []

query_index = 0
while query_index < len(queries):
query_type = int(queries[query_index])

if query_type == 1:
# Move query
direction = queries[query_index + 1]
dx, dy = direction_map[direction]

# Move the head
x[0] += dx
y[0] += dy

# Shift the rest of the parts
for i in range(1, N):
x[i], y[i] = x[i - 1], y[i - 1]

query_index += 2
elif query_type == 2:
# Query position
p = int(queries[query_index + 1]) - 1
output.append(f"{x[p]} {y[p]}")

query_index += 2

# Print all results for type 2 queries
print("\n".join(output))

if __name__ == "__main__":
main()
```		 [{"input": "5 9\n2 3\n1 U\n2 3\n1 R\n1 D\n2 3\n1 L\n2 1\n2 5\n", "output": "3 0\n2 0\n1 1\n1 0\n1 0\n", "testtype": "stdin"}]
deepseek-v3 ```python
# YOUR CODE HERE
import sys

def main():
input = sys.stdin.read
data = input().split()
idx = 0
N = int(data[idx])
Q = int(data[idx+1])
idx += 2

# Initialize the positions of the parts
parts = [(i, 0) for i in range(1, N+1)]

output = []
for _ in range(Q):
if data[idx] == '1':
C = data[idx+1]
idx += 2
# Move the head
x, y = parts[0]
if C == 'R':
x += 1
elif C == 'L':
x -= 1
elif C == 'U':
y += 1
elif C == 'D':
y -= 1
# Update the head position
parts[0] = (x, y)
# Move the other parts
for i in range(1, N):
parts[i] = parts[i-1]
else:
p = int(data[idx+1])
idx += 2
x, y = parts[p-1]
output.append(f"{x} {y}")

# Print the output
print("\n".join(output))

if __name__ == "__main__":
main()
```		 [{"input": "5 9\n2 3\n1 U\n2 3\n1 R\n1 D\n2 3\n1 L\n2 1\n2 5\n", "output": "3 0\n2 0\n1 1\n1 0\n1 0\n", "testtype": "stdin"}]