Time Limit: 10000/5000 MS (Java/Others)

Memory Limit: 130712/130712 K (Java/Others)

On a m*m land stationed n troops, numbered from 1 to n. The i-th troop's position can be described by two numbers (xi,yi) (1<=xi<=m,1<=yi<=m). It is possible that more than one troop stationed in the same place.

Then there are t minutes, in each minute one of the following two events will occur:

(1)the x-th troop moves towards a direction( Up(U) Down(D) Left(L) Right(R))for d units;(You can suppose that the troops won't move out of the boundary)

(2)the x-th troop needs to regroup the troops which stations in the same row or column with the x-th troop. That is, these troops need to move to the x-th troop's station.

Suggest the cost of i-th troop moving to the j-th troop is (xi-xj)^2+(yi-yj)^2, every time a troop regroups, you should output the cost of the regrouping modulo 10^9+7.

Then there are t minutes, in each minute one of the following two events will occur:

(1)the x-th troop moves towards a direction( Up(U) Down(D) Left(L) Right(R))for d units;(You can suppose that the troops won't move out of the boundary)

(2)the x-th troop needs to regroup the troops which stations in the same row or column with the x-th troop. That is, these troops need to move to the x-th troop's station.

Suggest the cost of i-th troop moving to the j-th troop is (xi-xj)^2+(yi-yj)^2, every time a troop regroups, you should output the cost of the regrouping modulo 10^9+7.

The first line: two numbers n,m(n<=100000,m<=10^18)

Next n lines each line contain two numbers xi,yi(1<=xi,yi<=m)

Next line contains a number t.(t<=100000)

Next t lines, each line's format is one of the following two formats:

(1)S x d, S∈{U,L,D,R}, indicating the first event(1<=x<=n,0<=d<m)

(2)Q x, indicating the second event(1<=x<=n)

In order to force you to answer the questions online, each time you read x', x=x'⊕lastans("⊕" means "xor"), where lastans is the previous answer you output. At the beginning lastans=0.

Next n lines each line contain two numbers xi,yi(1<=xi,yi<=m)

Next line contains a number t.(t<=100000)

Next t lines, each line's format is one of the following two formats:

(1)S x d, S∈{U,L,D,R}, indicating the first event(1<=x<=n,0<=d<m)

(2)Q x, indicating the second event(1<=x<=n)

In order to force you to answer the questions online, each time you read x', x=x'⊕lastans("⊕" means "xor"), where lastans is the previous answer you output. At the beginning lastans=0.

提交代码