1545: 阿正的排球测试

阿正今年的体育课选到了他心心念念的排球。众所周知，阿正的排球水平非常高，以至于体育老师在考试是对他“关照有加“。老师考核阿正的内容是两个人之间的传球，这导致阿正不得不向排球水平更高的Mickey同学寻求帮助——让Mickey同学做阿正传球的搭档。  

阿正需要和他的搭档不间断的传球若干次。由于Mickey同学的水平非常高，所以不需要考虑Mickey能否接到阿正同学传的球，只用考虑阿正能否接到Mickey同学传过来的球即可。  

假设Mickey和阿正同学进行排球传球只在一维方向上进行。我们以一个32位的“01数组（即只由数字0和数字1组成的数组）“来表示Mickey和阿正的传球场地，在此题中，我们称此“01数组”为S，由于只用考虑阿正能否接到Mickey传来的球，所以对于某个位置i（0<=i<=31），若S[i]=1，则这个位置表示Mikey传过来排球的一个可能的落点。  

现在给你一个十进制的整数，你需要先将这个十进制的整数转为32位的二进制数来获得Mikey传球所有可能的落点。（详请参考提示） 

现在以下标pos表示阿正在S上所处的位置。阿正同学有一个接球范围r，它可以接到落到下标为i，i属于[pos-r,pos+r] 内的所有球。  

但不幸的是，坏心眼的阿树这时候跑来捣乱了。坏心眼的阿树同学可以使用魔法干扰Mickey同学排球的落点，阿树同学的魔法种类有以下3种：  

1.      阿树同学对S上的某个点 i 的值与0进行按位与操作，即 使S[i]=S[i]&0；  

2.      阿树同学对S上的某个点 i 的值与0进行按位或操作，即 使S[i]=S[i]|0；  

3.      阿树同学对S上的某个点 i 的值与1进行按位异或操作，即 使S[i]=S[i]^1；  

现在你的任务是算出经过坏心眼的阿树捣乱后阿正同学接到Mickey传过来球的概率，这个概率以阿正可以接到的球的数量比上所有球可能落点的数量来表示。  

第一行一个十进制的正整数N，代表Mickey和阿正传球的场地。 

第二行三个整数pos，r和t，分别代表阿正的位置，阿正的接球半径和坏心眼的阿树使用魔法的次数。 

随后t行每行两个整数，分别代表坏心眼阿树使用魔法的种类和魔法处理的位置。（1代表与操作，2代表或操作，3代表异或操作）。 

输入保证0<=pos<=32，0<=r<=32，0<=t<=100000。 

1000000666
16 7 4
1 10
2 12
1 8
3 17

40.00%