胡散è‡ã„マジシャンãŒãƒžã‚¸ãƒƒã‚¯ã‚’披露ã™ã‚‹ã‚ˆã†ã§ã™ã€‚
「ã•ã¦ã€1ã¤ã®å¥½ããªæ•´æ•°ã‚’æ€ã„æµ®ã‹ã¹ã¦ãã ã•ã„。ã€
ã‚ãªãŸã¯ã€é ã®ä¸ã«è‡ªåˆ†ã®æ•°ãˆå¹´ã‚’æ€ã„æµ®ã‹ã¹ã‚‹ã“ã¨ã«ã—ã¾ã—ãŸã€‚
マジシャンã¯ã‚¯ã‚¨ãƒªã‚’ $N$ 回投ã’ã¦ãã¾ã—ãŸã€‚
å„クエリã¯ã€ä»¥ä¸‹ã®ã†ã¡ã®ã©ã‚Œã‹ã§ã™ã€‚
å„クエリã”ã¨ã«ã€æ€ã„æµ®ã‹ã¹ã¦ã„ã‚‹æ•°ã«å¯¾ã—ã¦ã‚¯ã‚¨ãƒªã‚’処ç†ã—ã€çµæžœã¨ã—ã¦å‡ºãŸå€¤ã‚’é ã®ä¸ã«æ€ã„æµ®ã‹ã¹ã¾ã™ã€‚
「ã•ã¦ã€ä»Šã‹ã‚‰æœ€åˆã«ã‚ãªãŸã®æ€ã„æµ®ã‹ã¹ãŸæ•°ã‚’当ã¦ã¦ã¿ã›ã¾ã—ょã†ã€‚ã€
ãã†ã„ã£ãŸãƒžã‚¸ã‚·ãƒ£ãƒ³ã¯ã€ä½•ã‹ã‚’言ãŠã†ã¨ã—ã¦ã„ã¾ã™ã€‚
ã—ã‹ã—ã€ä½•ã‚’言ãˆã°ã„ã„ã®ã‹å¿˜ã‚Œã¦ã—ã¾ã£ãŸã‚ˆã†ã§ã™ã€‚
胡散è‡ã„マジシャンã¯æ±—ダラダラã§ã‚ãªãŸã‚’見ã¤ã‚ã¦ã„ã¾ã™ã€‚
仕方ãŒãªã„ã®ã§ã€ä½•ã‚’言ãˆã°ã„ã„ã®ã‹æ•™ãˆã¦ã‚ã’ã¾ã—ょã†ã€‚
マジシャンã¯æœ€å¾Œã«ä»¥ä¸‹ã®ã‚ˆã†ã«è¨€ã†ã¤ã‚‚ã‚Šã ã£ãŸã‚ˆã†ã§ã™ã€‚
「今ã‚ãªãŸãŒæ€ã„æµ®ã‹ã¹ã¦ã„ã‚‹æ•´æ•°ã«ã€ $A$ を足ã—ã¦ã€ $B$ ã§å‰²ã‚Œã°ã€ãã‚Œã¯ã‚ãªãŸãŒæœ€åˆã«æ€ã„æµ®ã‹ã¹ãŸæ•´æ•°ãªã®ã§ã™ã€
制約ã‹ã‚‰ã€æ•´æ•°ã®çµ„ $(A,B)$ ã§ã‚ã£ã¦ã€æ€ã„æµ®ã‹ã¹ãŸæ•´æ•°ãŒã„ãã¤ã§ã‚ã£ã¦ã‚‚上ã®æ¡ä»¶ã‚’満ãŸã™ã‚‚ã®ãŒã€ãŸã 1ã¤ã«å®šã¾ã‚Šã¾ã™ã€‚
æ•´æ•°ã®çµ„ $(A,B)$ を求ã‚ã¦ãã ã•ã„。
ãŸã ã—〠$B$ 㯠$0$ ã§ã‚ã£ã¦ã¯ã„ã‘ã¾ã›ã‚“。
入力ã¯ä»¥ä¸‹ã®å½¢å¼ã§ä¸Žãˆã‚‰ã‚Œã‚‹ã€‚
$N$ $q_1$ $x_1$ $\vdots$ $q_n$ $x_n$
$1$ 行目ã«ä¸Žãˆã‚‰ã‚Œã‚‹ã‚¯ã‚¨ãƒªã®æ•° $N$ ãŒä¸Žãˆã‚‰ã‚Œã‚‹ã€‚
$2$ 行目ã‹ã‚‰ç¶šã $N$ è¡Œã«ã‚¯ã‚¨ãƒªã®æƒ…å ±ãŒä¸Žãˆã‚‰ã‚Œã‚‹ã€‚
$q$ ã¯ã‚¯ã‚¨ãƒªã®ç¨®é¡žã‚’表ã—ã€å•é¡Œæ–‡ä¸ã®ãƒªã‚¹ãƒˆã®æ•°å—ã«å¯¾å¿œã™ã‚‹ã€‚
入力ã¯ä»¥ä¸‹ã®æ¡ä»¶ã‚’満ãŸã™ã€‚
$1$ è¡Œã«æ¡ä»¶ã‚’満ãŸã™æ•´æ•° $A,B$ を空白区切りã§å‡ºåŠ›ã›ã‚ˆã€‚
3 1 2 2 10 3 8
-2 2
10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10 1 10
0 10000000000
32bitæ•´æ•°åž‹ã«ç”ãˆãŒåŽã¾ã‚‹ã¨ã¯é™ã‚‰ãªã„ã“ã¨ã«æ³¨æ„ã—ã¦ãã ã•ã„。