시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 32 MB 394 51 38 18.447%

문제

싸리와 버드는 정말 할 게 없어서 뒷뜰에 높이가 N인 피라미드를 만들고 그 위에 좋아하는 단어를 쓰기로 했다. 아래 그림처럼 단어를 반복해서 지그재그 모양으로 써 내려간다. 

     J
    N A
   J E T
  J A N I
 A N J E T
N A J A N I

버드는 피라미드의 K개의 줄을 고르고 각 줄을 ai라고 하고, 그 줄의 문자를 골라 ci라고 한다. 그리고 싸리에게 "ai행에 ci가 몇 번 나오게?"라고 묻는다. 싸리를 도와 버드의 질문에 대답해보자.

입력

첫째 줄은 정수 N(1 ≤ N ≤ 1018)이 주어진다. 

둘째 줄은 알파벳 대문자로 이루어진 단어가 주어진다. 단어의 길이는 106을 넘지 않는다.

셋째 줄은 정수 K(1 ≤ K ≤ 50,000)가 주어진다. (K는 버드가 고른 줄의 수이다.)

그 아래 K개의 줄에는 각각 ai, ci(1 ≤ ai ≤ N, ci는 알파벳) 쌍이 주어진다.

출력

K줄만큼 출력한다. i번째 줄은 ai행에 나오는 ci의 개수이다.

예제 입력 1

6
JANJETINA
5
1 J
1 A
6 N
6 I
5 E

예제 출력 1

1
0
2
1
1

예제 입력 2

5
A
5
1 A
2 A
3 A
4 A
5 B

예제 출력 2

1
2
3
4
0

예제 입력 3

3
AB
3
2 A
2 B
3 B

예제 출력 3

1
1
2
W3sicHJvYmxlbV9pZCI6IjEwNTQxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMmY4XHViOWFjXHVjNjQwIFx1YmM4NFx1YjRkY1x1Yzc1OCBcdWQ1M2NcdWI3N2NcdWJiZjhcdWI0ZGMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzJmOFx1YjlhY1x1YzY0MCBcdWJjODRcdWI0ZGNcdWIyOTQgXHVjODE1XHViOWQwIFx1ZDU2MCBcdWFjOGMgXHVjNWM2XHVjNWI0XHVjMTFjIFx1YjRiN1x1YjczMFx1YzVkMCBcdWIxOTJcdWM3NzRcdWFjMDAgTlx1Yzc3OCBcdWQ1M2NcdWI3N2NcdWJiZjhcdWI0ZGNcdWI5N2MgXHViOWNjXHViNGU0XHVhY2UwIFx1YWRmOCBcdWM3MDRcdWM1ZDAgXHVjODhiXHVjNTQ0XHVkNTU4XHViMjk0IFx1YjJlOFx1YzViNFx1Yjk3YyBcdWM0ZjBcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjYzk4XHViN2ZjIFx1YjJlOFx1YzViNFx1Yjk3YyBcdWJjMThcdWJjZjVcdWQ1NzRcdWMxMWMgXHVjOWMwXHVhZGY4XHVjN2FjXHVhZGY4IFx1YmFhOFx1YzU5MVx1YzczY1x1Yjg1YyBcdWMzNjggXHViMGI0XHViODI0XHVhYzA0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgIEpcclxuICAgIE4gQVxyXG4gICBKIEUgVFxyXG4gIEogQSBOIElcclxuIEEgTiBKIEUgVFxyXG5OIEEgSiBBIE4gSVxyXG48XC9wcmU+XHJcblxyXG48cD5cdWJjODRcdWI0ZGNcdWIyOTQgXHVkNTNjXHViNzdjXHViYmY4XHViNGRjXHVjNzU4Jm5ic3A7S1x1YWMxY1x1Yzc1OCZuYnNwO1x1YzkwNFx1Yzc0NCBcdWFjZTBcdWI5NzRcdWFjZTAgXHVhYzAxIFx1YzkwNFx1Yzc0NCZuYnNwO2E8c3ViPmk8XC9zdWI+XHViNzdjXHVhY2UwIFx1ZDU1OFx1YWNlMCwgXHVhZGY4IFx1YzkwNFx1Yzc1OCBcdWJiMzhcdWM3OTBcdWI5N2MgXHVhY2U4XHViNzdjIGM8c3ViPmk8XC9zdWI+XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YzJmOFx1YjlhY1x1YzVkMFx1YWM4YyAmcXVvdDthPHN1Yj5pPFwvc3ViPlx1ZDU4OVx1YzVkMCBjPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWJhODcgXHViYzg4IFx1YjA5OFx1YzYyNFx1YWM4Yz8mcXVvdDtcdWI3N2NcdWFjZTAgXHViYjNiXHViMjk0XHViMmU0LiBcdWMyZjhcdWI5YWNcdWI5N2MgXHViM2M0XHVjNjQwIFx1YmM4NFx1YjRkY1x1Yzc1OCBcdWM5YzhcdWJiMzhcdWM1ZDAgXHViMzAwXHViMmY1XHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1Yzc0MCBcdWM4MTVcdWMyMTggTigxICZsZTsgTiAmbGU7IDEwPHN1cD4xODxcL3N1cD4pXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1Yzc0MCBcdWM1NGNcdWQzMGNcdWJjYjMgXHViMzAwXHViYjM4XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWIyZThcdWM1YjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZThcdWM1YjRcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDEwPHN1cD42PFwvc3VwPlx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxNGJcdWM5ZjggXHVjOTA0XHVjNzQwIFx1YzgxNVx1YzIxOCBLKDEgJmxlOyBLICZsZTsgNTAsMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChLXHViMjk0Jm5ic3A7XHViYzg0XHViNGRjXHVhYzAwIFx1YWNlMFx1Yjk3OCBcdWM5MDRcdWM3NTggXHVjMjE4XHVjNzc0XHViMmU0Lik8XC9wPlxyXG5cclxuPHA+XHVhZGY4IFx1YzU0NFx1Yjc5OCBLXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDFcdWFjMDEgYTxzdWI+aTxcL3N1Yj4sIGM8c3ViPmk8XC9zdWI+KDEgJmxlOyBhPHN1Yj5pPFwvc3ViPiAmbGU7IE4sIGM8c3ViPmk8XC9zdWI+XHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMykmbmJzcDtcdWMzMGRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPktcdWM5MDRcdWI5Y2NcdWQwN2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBpXHViYzg4XHVjOWY4IFx1YzkwNFx1Yzc0MCBhPHN1Yj5pPFwvc3ViPlx1ZDU4OVx1YzVkMCBcdWIwOThcdWM2MjRcdWIyOTQgYzxzdWI+aTxcL3N1Yj5cdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwNTQxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUElSQU1JREEiLCJkZXNjcmlwdGlvbiI6IjxwPlpvcmFuIGFuZCBUb21pc2xhdiBkb24mIzM5O3QgcmVhbGx5IGhhdmUgYW55dGhpbmcgaW1wb3J0YW50IHRvIGRvLCBzbyB0aGV5IHNwZW5kIHRoZWlyIGRheXMgZG9pbmcgdmFyaW91cyBhY3Rpdml0aWVzLiBUb2RheSwgdGhleSBidWlsdCBhIHB5cmFtaWQgb2YgdGhlIGhlaWdodCBOIGluIHRoZSBiYWNrIGdhcmRlbiBhbmQgd3JvdGUgdGhlaXIgZmF2b3JpdGUgd29yZCBvbiBpdCwgcmVwZWF0aW5nIGl0IGZyb20gbGluZSB0byBsaW5lIGFuZCBjaGFuZ2luZyBkaXJlY3Rpb24sIGFzIHNob3duIGluIHRoZSBwaWN0dXJlLjxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgIEpcclxuICAgIE4gQVxyXG4gICBKIEUgVFxyXG4gIEogQSBOIElcclxuIEEgTiBKIEUgVFxyXG5OIEEgSiBBIE4gSVxyXG5cclxuUHlyYW1pZCBvZiB0aGUgaGVpZ2h0IDYgbWFya2VkIHdpdGggdGhlIHdvcmQgJnF1b3Q7SkFOSkVUSU5BJnF1b3Q7XHJcbjxcL3ByZT5cclxuXHJcbjxwPlRvbWlzbGF2IGhhcyBub3cgY2hvc2VuIEsgbGluZXMgb2YgdGhlIHB5cmFtaWQsIG1hcmtlZCB3aXRoIGFpLCBhbmQgaGFzIGNob3NlbiBhIGxldHRlciBjaSBmb3IgZWFjaCBsaW5lLiBUaGVuIGhlIGFza2VkIFpvcmFuIEsgdHJpY2t5IHF1ZXN0aW9uczogJnF1b3Q7SG93IG1hbnkgdGltZXMgZG9lcyB0aGUgbGV0dGV0IGNpIGFwcGVhciBpbiB0aGUgcm93IGFpPyZxdW90OzxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIFpvcmFuJiMzOTtzIGNvdW5zZWxvci4gV3JpdGUgYSBwcm9ncmFtbWUgdGhhdCB3aWxsLCBmb3IgdGhlIGdpdmVuIHB5cmFtaWQgaGVpZ2h0IGFuZCB0aGVpciBmYXZvcml0ZSB3b3JkLCBhbnN3ZXIgVG9taXNsYXYmIzM5O3MgcXVlc3Rpb25zLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDxzdXA+MTg8XC9zdXA+KS48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgd29yZCB0aGF0IGNvbnNpc3RzIG9mIG9ubHkgdXBwZXJjYXNlIGxldHRlcnMgb2YgdGhlIEVuZ2xpc2ggYWxwaGFiZXQuIFRoZSB3b3JkJiMzOTtzIGxlbmd0aCB3aWxsIG5vdCBleGNlZWQgMTA8c3VwPjY8XC9zdXA+LjxcL3A+XHJcblxyXG48cD5UaGUgdGhpcmQgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgaW50ZWdlciBLICgxICZsZTsgSyAmbGU7IDUwIDAwMCksIHRoZSBudW1iZXIgb2YgbGluZXMgVG9taXNsYXYgaGFzIGNob3Nlbi48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIEsgbGluZXMgY29udGFpbnMgdGhlIHBhaXIgYTxzdWI+aTxcL3N1Yj4sIGM8c3ViPmk8XC9zdWI+ICgxICZsZTsgYTxzdWI+aTxcL3N1Yj4gJmxlOyBOLCBjPHN1Yj5pPFwvc3ViPiB1cHBlcmNhc2UgbGV0dGVyIG9mIHRoZSBFbmdsaXNoIGFscGhhYmV0KSB3aGljaCByZXByZXNlbnQgVG9taXNsYXYmIzM5O3MgcXVlc3Rpb25zLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBLIGxpbmVzLiBUaGUgaXRoIGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiBhIHNpbmdsZSBpbnRlZ2VyIC0gdGhlIG51bWJlciBvZiBhcHBlYXJhbmNlcyBvZiBsZXR0ZXIgYzxzdWI+aTxcL3N1Yj4gaW4gdGhlIHJvdyBhPHN1Yj5pPFwvc3ViPi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2014/2015 > Contest #1 3번

  • 문제의 오타를 찾은 사람: cokcjswo
  • 잘못된 번역을 찾은 사람: Green55
  • 문제를 번역한 사람: yang