Code-Golf: Lights Off! The shortest code to pass all possibilities wins

Many grid based games have been made that start off with a grid of lights that are switched on.  Pressing any of the lights causes that light and the four lights adjacent to it to be toggled.  When a light is toggled, it is turned off or turned on, depending on if it was intially turned on or off.  The goal is to hit the lights in a sequence that results in all of the lights being turned off at the end.

"X" represents lights that are turned on.  "O" represents lights that are turned off.  "P" represents that square that is pressed.

XOO          XOO      XOX      XOX      XXX
XOX          XOP  -&gt;  XXO  -&gt;  OPO  -&gt;  XOX
OOX          OOX      POO      XXO      XOO

Intial Grid  Press 1  Press 2  Press 3  Ending Grid


Input can be taken directly from a file passed as an argument, or as standard input.  The first line of input will contain x (1 &lt;= x &lt;= 20), the size of the grid of lights, meaning x by x.  The second line will contain y (0 &lt;= y &lt;= (x * 3)2), the number of lights initially lit up.  The next y lines contain coordinates of lit up lights on the grid, in the format of "row column".  Lights that are already switched on (have been toggled previously) should be toggled off again.  The next line will contain z, the number of lights pressed.  The final z lines contain coordinates of the pressed lights, in the order that they were pressed, in the format of "row column".

No input will be incorrect.  All numbers will be within the given boundaries of the grid.

The output will be the final grid after all lights have been toggled.  It should be an n by n grid.  For each area that has a light which is on, the uppercase character "X" should be used.  For each area that has a light which is off, the uppercase character "O" should be used.

Lights that are affected that are off the grid should be ignored.  Toggling a light on the edge of a grid should only affect the lights that are on the grid itself.

Test Cases



Input

4
5
2 3
2 4
3 1
3 4
4 3
7
3 3
4 4
3 4
4 2
4 1
2 2
3 2


Output

OXOO
XOXO
XOXO
OXOO




Input

1
3
1 1
1 1
1 1
2
1 1
1 1


Output

X
Python, 209 203 199 characters

I=input
x=I()+1
s=0
C=lambda:eval(raw_input().replace(' ','*%d+'%x))
exec's^=1&lt;&lt;C();'*I()
exec's^=1+(7&lt;&lt;x)/2+(1&lt;&lt;x&lt;&lt;x)&lt;&lt;(C()-x);'*I()
R=range(1,x)
for r in R:print''.join('OX'[s&gt;&gt;r*x+c&amp;1]for c in R)


The state of the lights is kept in a single (big) integer variable, s.  XORs with bitmasks are used to toggle the lights.  I keep an extra bit per row to prevent wraparound.