C. Letters

time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

There are $\mathrm{nn dormitories\; in\; Berland\; State\; University,\; they\; are\; numbered\; with\; integers\; from 11 to nn.\; Each\; dormitory\; consists\; of\; rooms,\; there\; are aiai rooms\; in ii-th\; dormitory.\; The\; rooms\; in ii-th\; dormitory\; are\; numbered\; from 11 to aiai.}$

A postman delivers letters. Sometimes there is no specific dormitory and room number in it on an envelope. Instead of it only a room number among all rooms of all $\mathrm{nn dormitories\; is\; written\; on\; an\; envelope.\; In\; this\; case,\; assume\; that\; all\; the\; rooms\; are\; numbered\; from 11 to a1+a2+\cdots +ana1+a2+\cdots +an and\; the\; rooms\; of\; the\; first\; dormitory\; go\; first,\; the\; rooms\; of\; the\; second\; dormitory\; go\; after\; them\; and\; so\; on.}$

For example, in case $\mathrm{n=2n=2, a1=3a1=3 and a2=5a2=5 an\; envelope\; can\; have\; any\; integer\; from 11 to 88 written\; on\; it.\; If\; the\; number 77 is\; written\; on\; an\; envelope,\; it\; means\; that\; the\; letter\; should\; be\; delivered\; to\; the\; room\; number 44 of\; the\; second\; dormitory.}$

For each of $\mathrm{mm letters\; by\; the\; room\; number\; among\; all nn dormitories,\; determine\; the\; particular\; dormitory\; and\; the\; room\; number\; in\; a\; dormitory\; where\; this\; letter\; should\; be\; delivered.}$

Input

The first line contains two integers $\mathrm{nn and mm (1\le n,m\le 2\cdot 105)(1\le n,m\le 2\cdot 105) —\; the\; number\; of\; dormitories\; and\; the\; number\; of\; letters.}$

The second line contains a sequence ${\mathrm{a1,a2,\dots ,ana1,a2,\dots ,an (1\le ai\le 1010)(1\le ai\le 1010),\; where aiai equals\; to\; the\; number\; of\; rooms\; in\; the ii-th\; dormitory.\; The\; third\; line\; contains\; a\; sequence b1,b2,\dots ,bmb1,b2,\dots ,bm (1\le bj\le a1+a2+\cdots +an)(1\le bj\le a1+a2+\cdots +an),\; where bjbj equals\; to\; the\; room\; number\; (among\; all\; rooms\; of\; all\; dormitories)\; for\; the jj-th\; letter.\; All bjbj are\; given\; in increasing order.}}^{}$

Output

Print $\mathrm{mm lines.\; For\; each\; letter\; print\; two\; integers ff and kk —\; the\; dormitory\; number ff (1\le f\le n)(1\le f\le n) and\; the\; room\; number kk in\; this\; dormitory (1\le k\le af)(1\le k\le af) to\; deliver\; the\; letter.}$

Examples

input

Copy

3 6 10 15 12 1 9 12 23 26 37

output

Copy

1 1 1 9 2 2 2 13 3 1 3 12

input

Copy

2 3 5 10000000000 5 6 9999999999

output

Copy

1 5 2 1 2 9999999994

Note

In the first example letters should be delivered in the following order:

• the first letter in room $\mathrm{11 of\; the\; first\; dormitory}$
• the second letter in room $\mathrm{99 of\; the\; first\; dormitory}$
• the third letter in room $\mathrm{22 of\; the\; second\; dormitory}$
• the fourth letter in room $\mathrm{1313 of\; the\; second\; dormitory}$
• the fifth letter in room $\mathrm{11 of\; the\; third\; dormitory}$
• the sixth letter in room $\mathrm{1212 of\; the\; third\; dormitory}$

$\mathrm{题意：n个宿舍，每个宿舍有ai个房间，再给你m个数，问每个数在第几个宿舍的第几个房间。}$

$\mathrm{分析：很简单的模拟，但是数据量很大，a数组里面每个数都要是long\; long，而且如果直接遍历求解的话会T掉，我第一个想到的就是学长在寒假教过的二分查找，很长时间没写二分有点忘。。。改了几次才过了样例，然后交上去就过了}$

1 #include 
      
        2 using namespace std; 3 #define fi first 4 #define se second 5 #define ll long long 6 #define pb push_back 7 const int N=2e5+5; 8 ll a[N]; 9 ll b[N];10 int main()11 {12     int n,m;13     scanf("%d %d",&n,&m);14     for (int i=1;i<=n;i++)15     {16         scanf("%I64d",&a[i]);17         b[1]=a[1];18         b[i]=b[i-1]+a[i];19     }20     int flag1,flag2;21     while(m--)22     {23         int flag;24         ll t;25         scanf("%I64d",&t);26         ll l=0,r=n;27         while(l+1
       
        t)    flag=1;31             if(b[mid]<=t)   flag=2;32             if(flag==1) r=mid;33             else if(flag==2)    l=mid;34         }35         if(t-b[l]==0)36             printf("%I64d %I64d\n",l,a[l]);37         else printf("%I64d %I64d\n",l+1,t-b[l]);38     }39 }