Синдзюкудағы бір көшеге зұлым рух еніп кетті. Бұл көше сол жақ шетіндегі кіреберіс пен оң жақ шетіндегі шығаберісті қосатын кесінді пішіндес, ал екі шеткі нүктенің арақашықтығы $10^9 + 1$-ге тең.

Көше бойында $N$ сиқыршы тұр. Сиқыршылар кіреберіске жақын орналасу ретімен $1$-ден $N$-ге дейінгі бүтін сандармен нөмірленген. $i$-ші сиқыршы кіреберістен оңға қарай $X_i$ ($X_i$ — оң бүтін сан) қашықтықта орналасқан, және барлық сиқыршылар әртүрлі орындарда тұр. Сонымен қатар әр сиқыршының қызыл немесе көк түстің біреуі бар.

Әрбір қарғыс екі бүтін санмен $a, b$ беріледі. Зұлым рух $a$-шы және $b$-шы сиқыршыларға қарғыс салады, әрі әрқашан $1 \le a < b \le N$ шарты орындалады. Осы кезде екі сиқыршыны қосатын кесіндінің үстінде қарғыс аймағы пайда болады, ал қарғыс аймағы $[X_a, X_b]$ кесіндісі болып табылады.

Қарғыс аймағы пайда болғанда, сиқыршылар қарғыс аймағының бойынан бір нүктені таңдап, оны өзекті орын ретінде белгілейді. Өзекті орынның координатасы нақты сан болуы мүмкін. Өзекті орынды $c$ деп белгілейік. Өзекті орын сиқыршы тұрған орынмен беттесуі де мүмкін.

Өзекті орын белгіленген соң, қарғыс аймағы келесі ережеге сәйкес қызыл жын қуу аймағы мен көк жын қуу аймағына бөлінеді.

Әрбір $a \le i < b$ үшін көршілес екі сиқыршының арасындағы $[X_i, X_{i+1}]$ кесіндісін қарастырайық.

• Егер $X_{i+1} \le c$ болса, онда $[X_i, X_{i+1}]$ кесіндісі толығымен $i$-ші сиқыршының түсіне ие жын қуу аймағына айналады.
• Егер $c \le X_i$ болса, онда $[X_i, X_{i+1}]$ кесіндісі толығымен $i+1$-ші сиқыршының түсіне ие жын қуу аймағына айналады.
• Егер $X_i < c < X_{i+1}$ болса, онда $[X_i, c]$ кесіндісі $i$-ші сиқыршының түсіне ие жын қуу аймағына, ал $[c, X_{i+1}]$ кесіндісі $i+1$-ші сиқыршының түсіне ие жын қуу аймағына айналады.

Яғни, өзекті орын $c$-ны негізге алғанда, сол жақтағы бөлік сол жақ шеткі нүктедегі сиқыршының түсіне, ал оң жақтағы бөлік оң жақ шеткі нүктедегі сиқыршының түсіне ие болады.

Жоғарыдағы ереже бойынша қарғыс аймағының барлық нүктелері жын қуу аймақтарымен жабылады, ал әртүрлі жын қуу аймақтары тек шеткі нүктелерінде ғана түйісе алады.

Өзекті орын $c$ болған кезде, қызыл жын қуу аймақтарының жалпы ұзындығын $R(c)$, ал көк жын қуу аймақтарының жалпы ұзындығын $B(c)$ деп белгілейік. Осы жын қуу рәсімінің үйлесімсіздігі — осы екі мәннің айырмасының модулі, яғни $|R(c) - B(c)|$.

Жын қуу рәсімінің сәтті өту ықтималдығын арттыру үшін сиқыршылар өзекті орын $c$-ны үйлесімсіздік ең кіші болатындай етіп оңтайлы таңдағысы келеді.

Сиқыршылар туралы деректер мен зұлым рух салатын қарғыстар туралы деректер берілгенде, әрбір қарғыс үшін жын қуу рәсімінің ең кіші үйлесімсіздігін табатын программа жазыңыз.

Кіріс деректер

Бірінші жолда бос орын арқылы сиқыршылардың саны $N$ мен қарғыстардың саны $Q$ беріледі. ($2 \le N \le 200\,000$; $1 \le Q \le 200\,000$)

Екінші жолдан бастап $N$ жолда бос орын арқылы сиқыршының координатасы $X_i$ мен түсі $C_i$ беріледі. ($1 \le X_1 < X_2 < \dots < X_N \le 10^9$, $C_i =$ R немесе B)

Одан кейінгі $Q$ жолда бос орын арқылы қарғыстың сипаттамасы $a, b$ беріледі. $a$ мен $b$ — зұлым рух қарғыс салатын екі сиқыршының нөмірлері. ($1 \le a < b \le N$)

Шығыс деректер

Әрбір қарғыс үшін жеке жолға сол қарғысқа сәйкес ең кіші үйлесімсіздікті шығарыңыз. Ең кіші үйлесімсіздік әрқашан бүтін сан болатынын дәлелдеуге болады.

Мысалдар

Кіріс деректер 1

4 2
1 R
6 B
8 B
12 R
1 4
2 3

Шығыс деректер 1

0
2

Ескертпе

1-қарғыс: Егер өзекті орынды $c = 2.5$ деп белгілесек, $[1, 2.5]$ және $[8, 12]$ кесінділері қызыл жын қуу аймағына, ал $[2.5, 6]$ және $[6, 8]$ кесінділері көк жын қуу аймағына айналады. Қызыл жын қуу аймақтарының жалпы ұзындығы мен көк жын қуу аймақтарының жалпы ұзындығының екеуі де $5.5$-ке тең болғандықтан, үйлесімсіздік $0$-ге тең. Өзекті орынды $c = 11.5$ деп белгілесек те, үйлесімсіздік $0$ болады.

2-қарғыс: Егер өзекті орынды $c = 8$ деп белгілесек, $[6, 8]$ кесіндісі толығымен көк жын қуу аймағына айналады. Қарғыс аймағында қызыл сиқыршы болмағандықтан, үйлесімсіздікті $2$-ден кіші ету мүмкін емес.