c++/2430: subscripting very much slower than pointer arithmetic

[warren at euphrates dot com]

>Number:         2430
>Category:       c++
>Synopsis:       subscripting very much slower than pointer arithmetic
>Confidential:   no
>Severity:       serious
>Priority:       high
>Responsible:    unassigned
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Fri Mar 30 00:16:00 PST 2001
>Closed-Date:
>Last-Modified:
>Originator:     Warren Reier
>Release:        gcc 2.95.2 and gcc 2.95.3
>Organization:
>Environment:
Solaris 2.7, Sparc 5
>Description:
Compiled attached C++ program, was very surprised by slowness of first test.  Made the following change:

256,258c256
<       const int                       size = last - first;
< //for (int n = 0; n < size; ++n) result += first[n];
<       for (double* p = first; p <= last; p++) result += *p;
---
>     for (int n = 0; n < last - first; ++n) result += first[n];

Speed of first test more than doubled.  
>How-To-Repeat:
1. compile with -O2 -fomit-frame-pointer
2. run program
3, make above change to source and rerun
>Fix:

>Release-Note:
>Audit-Trail:
>Unformatted:
----gnatsweb-attachment----
Content-Type: unknown; name="stepanov_v1p2.C"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="stepanov_v1p2.C"

LyogS0FJJ3MgdmVyc2lvbiBvZiBTdGVwYW5vdiBCZW5jaG1hcmsgLS0gVmVyc2lvbiAxLjIKCiAg
IFZlcnNpb24gMS4yIC0tIHJlbW92ZWQgc29tZSBzcGVjaWFsIGNvZGUgZm9yIEdOVSBzeXN0ZW1z
IHRoYXQKCQkgIEdOVSBjb21wbGFpbmVkIGFib3V0IHdpdGhvdXQgLU8KClRvIHZlcmlmeSBob3cg
ZWZmaWNpZW50bHkgQysrIChhbmQgaW4gcGFydGljdWxhciBTVEwpIGlzIGNvbXBpbGVkIGJ5CnRo
ZSBwcmVzZW50IGRheSBjb21waWxlcnMsIEkgY29tcG9zZWQgYSBsaXR0bGUgYmVuY2htYXJrLiBJ
dCBvdXRwdXRzCjEzIG51bWJlcnMuIEluIHRoZSBpZGVhbCB3b3JsZCB0aGVzZSBudW1iZXJzIHNo
b3VsZCBiZSB0aGUgc2FtZS4gSW4KdGhlIHJlYWwgd29ybGQsIGhvd2V2ZXIsIC4uLgoKVGhlIGZp
bmFsIG51bWJlciBwcmludGVkIGJ5IHRoZSBiZW5jaG1hcmsgaXMgYSBnZW9tZXRyaWMgbWVhbiBv
ZiB0aGUKcGVyZm9ybWFuY2UgZGVncmFkYXRpb24gZmFjdG9ycyBvZiBpbmRpdmlkdWFsIHRlc3Rz
LiBJdCBjbGFpbXMgdG8KcmVwcmVzZW50IHRoZSBmYWN0b3IgYnkgd2hpY2ggeW91IHdpbGwgYmUg
cHVuaXNoZWQgYnkgeW91cgpjb21waWxlciBpZiB5b3UgYXR0ZW1wdCB0byB1c2UgQysrIGRhdGEg
YWJzdHJhY3Rpb24gZmVhdHVyZXMuIEkgY2FsbAp0aGlzIG51bWJlciAiQWJzdHJhY3Rpb24gUGVu
YWx0eS4iCgpBcyB3aXRoIGFueSBiZW5jaG1hcmsgaXQgaXMgaGFyZCB0byBwcm92ZSBzdWNoIGEg
Y2xhaW07IHNvbWUgcGVvcGxlCnRvbGQgbWUgdGhhdCBpdCBkb2VzIG5vdCByZXByZXNlbnQgdHlw
aWNhbCBDKysgdXNhZ2UuIEl0IGlzLCBob3dldmVyLAphIG5vdGV3b3J0aHkgZmFjdCB0aGF0IG1h
am9yaXR5IG9mIHRoZSBwZW9wbGUgd2hvIHNvIG9iamVjdCBhcmUKcmVzcG9uc2libGUgZm9yIEMr
KyBjb21waWxlcnMgd2l0aCBkaXNwcm9wb3J0aW9uYXRseSBsYXJnZSBBYnN0cmFjdGlvbgpQZW5h
bHR5LgoKVGhlIHN0cnVjdHVyZSBvZiB0aGUgYmVuY2htYXJrIGlzIHJlYWxseSBxdWl0ZSBzaW1w
bGUuIEl0IGFkZHMgMjAwMApkb3VibGVzIGluIGFuIGFycmF5IDI1MDAwIHRpbWVzLiBJdCBkb2Vz
IGl0IGluIDEzIGRpZmZlcmVudCB3YXlzIHRoYXQKaW50cm9kdWNlIG1vcmUgYW5kIG1vcmUgYWJz
dHJhY3Qgd2F5cyBvZiBkb2luZyBpdDoKCjAgLSB1c2VzIHNpbXBsZSBGb3J0cmFuLWxpa2UgZm9y
IGxvb3AuCjEgLSAxMiB1c2UgU1RMIHN0eWxlIGFjY3VtdWxhdGUgdGVtcGxhdGUgZnVuY3Rpb24g
d2l0aCBwbHVzIGZ1bmN0aW9uIG9iamVjdC4KMSwgMywgNSwgNyAsOSwgMTEgdXNlIGRvdWJsZXMu
CjIsIDQsIDYsIDgsIDEwLCAxMiB1c2UgRG91YmxlIC0gZG91YmxlIHdyYXBwZWQgaW4gYSBjbGFz
cy4KMSwgMiAtIHVzZSByZWd1bGFyIHBvaW50ZXJzLgozLCA0IC0gdXNlIHBvaW50ZXJzIHdyYXBw
ZWQgaW4gYSBjbGFzcy4KNSwgNiAtIHVzZSBwb2ludGVycyB3cmFwcGVkIGluIGEgcmV2ZXJzZS1p
dGVyYXRvciBhZGFwdG9yLgo3LCA4IC0gdXNlIHdyYXBwZWQgcG9pbnRlcnMgd3JhcHBlZCBpbiBh
IHJldmVyc2UtaXRlcmF0b3IgYWRhcHRvci4KOSwgMTAgLSB1c2UgcG9pbnRlcnMgd3JhcHBlZCBp
biBhIHJldmVyc2UtaXRlcmF0b3IgYWRhcHRvciB3cmFwcGVkIGluIGEKICByZXZlcnNlLWl0ZXJh
dG9yIGFkYXB0b3IuCjExLCAxMiAtIHVzZSB3cmFwcGVkIHBvaW50ZXJzIHdyYXBwZWQgaW4gYSBy
ZXZlcnNlLWl0ZXJhdG9yIGFkYXB0b3Igd3JhcHBlZAogIGluIGEgcmV2ZXJzZS1pdGVyYXRvciBh
ZGFwdG9yLgoKQWxsIHRoZSBvcGVyYXRvcnMgb24gRG91YmxlIGFuZCBkaWZmZXJlbnQgcG9pbnRl
ci1saWtlIGNsYXNzZXMgYXJlCmRlY2xhcmVkIGlubGluZS4gVGhlIG9ubHkgdGhpbmcgdGhhdCBp
cyByZWFsbHkgbWVhc3VyZWQgaXMgdGhlIHBlbmFsdHkKZm9yIGRhdGEgYWJzdHJhY3Rpb24uIFdo
aWxlIHRlbXBsYXRlcyBhcmUgdXNlZCwgdGhleSBkbyBub3QgY2F1c2UgYW55CnBlcmZvcm1hbmNl
IGRlZ3JhZGF0aW9uLiBUaGV5IGFyZSB1c2VkIG9ubHkgdG8gc2ltcGxpZnkgdGhlIGNvZGUuCgpT
aW5jZSBtYW55IG9mIHlvdSBhcmUgaW50ZXJlc3RlZCBpbiB0aGUgQysrIHBlcmZvcm1hbmNlIGlz
c3VlcywgSQpkZWNpZGVkIHRvIHBvc3QgdGhlIGJlbmNobWFyayBoZXJlLiBJIHdvdWxkIGFwcHJl
Y2lhdGUgaWYgeW91IHJ1biBpdAphbmQgKGlmIHBvc3NpYmxlKSBzZW5kIG1lIHRoZSByZXN1bHRz
IGluZGljYXRpbmcgd2hhdCB5b3UgaGF2ZQpjb21waWxlZCBpdCB3aXRoIChDUFUsIGNsb2NrIHJh
dGUsIGNvbXBpbGVyLCBvcHRpbWl6YXRpb24gbGV2ZWwpLiBJdAppcyBzZWxmIGNvbnRhaW5lZCBh
bmQgd3JpdHRlbiBzbyB0aGF0IGl0IGNvdWxkIGJlIGNvbXBpbGVkIGV2ZW4gd2l0aAp0aG9zZSBj
b21waWxlcnMgdGhhdCBhdCBwcmVzZW50IGNhbm5vdCBjb21waWxlIFNUTCBhdCBhbGwuCgpJdCB0
YWtlcyBhIGZhaXJseSBsb25nIHRpbWUgdG8gcnVuIC0gb24gYSByZWFsbHkgc2xvdyBtYWNoaW5l
IGl0IG1pZ2h0CnRha2UgYSBmdWxsIGhvdXIuIChGb3IgdGhvc2Ugb2YgeW91IHdobyB3YW50IHRv
IHJ1biBpdCBmYXN0ZXIgLSBnaXZlCml0IGEgY29tbWFuZCBsaW5lIGFyZ3VtZW50IHRoYXQgc3Bl
Y2lmaWVzIHRoZSBudW1iZXIgb2YKaXRlcmF0aW9ucy4gVGhlIGRlZmF1bHQgaXMgMjUwMDAsIGJ1
dCBpdCBnaXZlcyBhbiBhY2N1cmF0ZSBwcmVkaWN0aW9ucwpldmVuIHdpdGggNTAwIG9yIGEgdGhv
dXNhbmQuKQoKCkFsZXggU3RlcGFub3YKc3RlcGFub3ZAbXRpLnNnaS5jb20KCiovCgoKI2luY2x1
ZGUgPHN0ZGRlZi5oPgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPHRpbWUuaD4KI2luY2x1
ZGUgPG1hdGguaD4KI2luY2x1ZGUgPHN0ZGxpYi5oPgoKdGVtcGxhdGUgPGNsYXNzIFQ+CmlubGlu
ZSBpbnQgb3BlcmF0b3IhPShjb25zdCBUJiB4LCBjb25zdCBUJiB5KSB7CiAgcmV0dXJuICEoeCA9
PSB5KTsKfQoKc3RydWN0IERvdWJsZSB7CiAgZG91YmxlIHZhbHVlOwogIERvdWJsZSgpIHt9CiAg
RG91YmxlKGNvbnN0IGRvdWJsZSYgeCkgOiB2YWx1ZSh4KSB7fQogIG9wZXJhdG9yIGRvdWJsZSgp
IHsgcmV0dXJuIHZhbHVlOyB9Cn07CgppbmxpbmUgRG91YmxlIG9wZXJhdG9yKyhjb25zdCBEb3Vi
bGUmIHgsIGNvbnN0IERvdWJsZSYgeSkgewogIHJldHVybiBEb3VibGUoeC52YWx1ZSArIHkudmFs
dWUpOwp9CgpzdHJ1Y3QgZG91YmxlX3BvaW50ZXIgewogICAgZG91YmxlKiBjdXJyZW50OwogICAg
ZG91YmxlX3BvaW50ZXIoKSB7fQogICAgZG91YmxlX3BvaW50ZXIoZG91YmxlKiB4KSA6IGN1cnJl
bnQoeCkge30KICAgIGRvdWJsZSYgb3BlcmF0b3IqKCkgY29uc3QgeyByZXR1cm4gKmN1cnJlbnQ7
IH0KICAgIGRvdWJsZV9wb2ludGVyJiBvcGVyYXRvcisrKCkgewoJKytjdXJyZW50OwoJcmV0dXJu
ICp0aGlzOwogICAgfQogICAgZG91YmxlX3BvaW50ZXIgb3BlcmF0b3IrKyhpbnQpIHsKCWRvdWJs
ZV9wb2ludGVyIHRtcCA9ICp0aGlzOwoJKysqdGhpczsKCXJldHVybiB0bXA7CiAgICB9CiAgICBk
b3VibGVfcG9pbnRlciYgb3BlcmF0b3ItLSgpIHsKCS0tY3VycmVudDsKCXJldHVybiAqdGhpczsK
ICAgIH0KICAgIGRvdWJsZV9wb2ludGVyIG9wZXJhdG9yLS0oaW50KSB7Cglkb3VibGVfcG9pbnRl
ciB0bXAgPSAqdGhpczsKCS0tKnRoaXM7CglyZXR1cm4gdG1wOwogICAgfQp9OwoKCmlubGluZSBp
bnQgb3BlcmF0b3I9PShjb25zdCBkb3VibGVfcG9pbnRlciYgeCwKCQkgICAgICBjb25zdCBkb3Vi
bGVfcG9pbnRlciYgeSkgewogICAgcmV0dXJuIHguY3VycmVudCA9PSB5LmN1cnJlbnQ7Cn0KCnN0
cnVjdCBEb3VibGVfcG9pbnRlciB7CiAgICBEb3VibGUqIGN1cnJlbnQ7CiAgICBEb3VibGVfcG9p
bnRlcigpIHt9CiAgICBEb3VibGVfcG9pbnRlcihEb3VibGUqIHgpIDogY3VycmVudCh4KSB7fQog
ICAgRG91YmxlJiBvcGVyYXRvciooKSBjb25zdCB7IHJldHVybiAqY3VycmVudDsgfQogICAgRG91
YmxlX3BvaW50ZXImIG9wZXJhdG9yKysoKSB7CgkrK2N1cnJlbnQ7CglyZXR1cm4gKnRoaXM7CiAg
ICB9CiAgICBEb3VibGVfcG9pbnRlciBvcGVyYXRvcisrKGludCkgewoJRG91YmxlX3BvaW50ZXIg
dG1wID0gKnRoaXM7CgkrKyp0aGlzOwoJcmV0dXJuIHRtcDsKICAgIH0KICAgIERvdWJsZV9wb2lu
dGVyJiBvcGVyYXRvci0tKCkgewoJLS1jdXJyZW50OwoJcmV0dXJuICp0aGlzOwogICAgfQogICAg
RG91YmxlX3BvaW50ZXIgb3BlcmF0b3ItLShpbnQpIHsKCURvdWJsZV9wb2ludGVyIHRtcCA9ICp0
aGlzOwoJLS0qdGhpczsKCXJldHVybiB0bXA7CiAgICB9Cn07CgoKaW5saW5lIGludCBvcGVyYXRv
cj09KGNvbnN0IERvdWJsZV9wb2ludGVyJiB4LAoJCSAgICAgICBjb25zdCBEb3VibGVfcG9pbnRl
ciYgeSkgewogICAgcmV0dXJuIHguY3VycmVudCA9PSB5LmN1cnJlbnQ7Cn0KCnRlbXBsYXRlIDxj
bGFzcyBSYW5kb21BY2Nlc3NJdGVyYXRvciwgY2xhc3MgVD4Kc3RydWN0IHJldmVyc2VfaXRlcmF0
b3IgewogICAgUmFuZG9tQWNjZXNzSXRlcmF0b3IgY3VycmVudDsKICAgIHJldmVyc2VfaXRlcmF0
b3IoUmFuZG9tQWNjZXNzSXRlcmF0b3IgeCkgOiBjdXJyZW50KHgpIHt9CiAgICBUJiBvcGVyYXRv
ciooKSBjb25zdCB7CiAgICAgIFJhbmRvbUFjY2Vzc0l0ZXJhdG9yIHRtcCA9IGN1cnJlbnQ7CiAg
ICAgIHJldHVybiAqKC0tdG1wKTsKICAgIH0KICAgIHJldmVyc2VfaXRlcmF0b3I8UmFuZG9tQWNj
ZXNzSXRlcmF0b3IsIFQ+JiBvcGVyYXRvcisrKCkgewoJLS1jdXJyZW50OwoJcmV0dXJuICp0aGlz
OwogICAgfQogICAgcmV2ZXJzZV9pdGVyYXRvcjxSYW5kb21BY2Nlc3NJdGVyYXRvciwgVD4gb3Bl
cmF0b3IrKyhpbnQpIHsKICAgICAgcmV2ZXJzZV9pdGVyYXRvcjxSYW5kb21BY2Nlc3NJdGVyYXRv
ciwgVD4gdG1wID0gKnRoaXM7CgkrKyp0aGlzOwoJcmV0dXJuIHRtcDsKICAgIH0KICAgIHJldmVy
c2VfaXRlcmF0b3I8UmFuZG9tQWNjZXNzSXRlcmF0b3IsIFQ+JiBvcGVyYXRvci0tKCkgewoJKytj
dXJyZW50OwoJcmV0dXJuICp0aGlzOwogICAgfQogICAgcmV2ZXJzZV9pdGVyYXRvcjxSYW5kb21B
Y2Nlc3NJdGVyYXRvciwgVD4gb3BlcmF0b3ItLShpbnQpIHsKICAgICAgcmV2ZXJzZV9pdGVyYXRv
cjxSYW5kb21BY2Nlc3NJdGVyYXRvciwgVD4gdG1wID0gKnRoaXM7CgktLSp0aGlzOwoJcmV0dXJu
IHRtcDsKICAgIH0KfTsKCnRlbXBsYXRlIDxjbGFzcyBSYW5kb21BY2Nlc3NJdGVyYXRvciwgY2xh
c3MgVD4KaW5saW5lIGludCBvcGVyYXRvcj09KGNvbnN0IHJldmVyc2VfaXRlcmF0b3I8UmFuZG9t
QWNjZXNzSXRlcmF0b3IsIFQ+JiB4LAoJCSAgICAgIGNvbnN0IHJldmVyc2VfaXRlcmF0b3I8UmFu
ZG9tQWNjZXNzSXRlcmF0b3IsIFQ+JiB5KSB7CiAgICByZXR1cm4geC5jdXJyZW50ID09IHkuY3Vy
cmVudDsKfQoKc3RydWN0IHsKICBkb3VibGUgb3BlcmF0b3IoKShjb25zdCBkb3VibGUmIHgsIGNv
bnN0IGRvdWJsZSYgeSkge3JldHVybiB4ICsgeTsgfQogIERvdWJsZSBvcGVyYXRvcigpKGNvbnN0
IERvdWJsZSYgeCwgY29uc3QgRG91YmxlJiB5KSB7cmV0dXJuIHggKyB5OyB9Cn0gcGx1czsKCgp0
ZW1wbGF0ZSA8Y2xhc3MgSXRlcmF0b3IsIGNsYXNzIE51bWJlcj4KTnVtYmVyIGFjY3VtdWxhdGUo
SXRlcmF0b3IgZmlyc3QsIEl0ZXJhdG9yIGxhc3QsIE51bWJlciByZXN1bHQpIHsKICB3aGlsZSAo
Zmlyc3QgIT0gbGFzdCkgcmVzdWx0ID0gIHBsdXMocmVzdWx0LCAqZmlyc3QrKyk7CiAgcmV0dXJu
IHJlc3VsdDsKfQoKaW50IGl0ZXJhdGlvbnMgPSAyNTAwMDsKI2RlZmluZSBTSVpFIDIwMDAKCmlu
dCBjdXJyZW50X3Rlc3QgPSAwOwoKZG91YmxlIHJlc3VsdF90aW1lc1syMF07Cgp2b2lkIHN1bW1h
cml6ZSgpIHsKICBwcmludGYoIlxudGVzdCAgICAgIGFic29sdXRlICAgYWRkaXRpb25zICAgICAg
cmF0aW8gd2l0aFxuIik7CiAgcHJpbnRmKCJudW1iZXIgICAgdGltZSAgICAgICBwZXIgc2Vjb25k
ICAgICB0ZXN0MFxuXG4iKTsKICBpbnQgaTsKICBkb3VibGUgbWlsbGlvbnMgPSAoZG91YmxlKFNJ
WkUpICogaXRlcmF0aW9ucykvMTAwMDAwMC47CiAgZm9yIChpID0gMDsgaSA8IGN1cnJlbnRfdGVz
dDsgKytpKQogICAgcHJpbnRmKCIlMmkgICAgICAgJTUuMmZzZWMgICAgJTUuMmZNICAgICAgICAg
JS4yZlxuIiwKCSAgIGksCgkgICByZXN1bHRfdGltZXNbaV0sCgkgICBtaWxsaW9ucy9yZXN1bHRf
dGltZXNbaV0sCgkgICByZXN1bHRfdGltZXNbaV0vcmVzdWx0X3RpbWVzWzBdKTsKICBkb3VibGUg
Z21lYW5fdGltZXMgPSAwLjsKICBkb3VibGUgdG90YWxfYWJzb2x1dGVfdGltZXMgPSAwLjsgIC8v
IHNhbSBhZGRlZCAxMi8wNS85NQogIGRvdWJsZSBnbWVhbl9yYXRlID0gMC47CiAgZG91YmxlIGdt
ZWFuX3JhdGlvID0gMC47CiAgZm9yIChpID0gMDsgaSA8IGN1cnJlbnRfdGVzdDsgKytpKSB7CiAg
ICB0b3RhbF9hYnNvbHV0ZV90aW1lcyArPSByZXN1bHRfdGltZXNbaV07ICAvLyBzYW0gYWRkZWQg
MTIvMDUvOTUKICAgIGdtZWFuX3RpbWVzICs9IGxvZyhyZXN1bHRfdGltZXNbaV0pOwogICAgZ21l
YW5fcmF0ZSAgKz0gbG9nKG1pbGxpb25zL3Jlc3VsdF90aW1lc1tpXSk7CiAgICBnbWVhbl9yYXRp
byArPSBsb2cocmVzdWx0X3RpbWVzW2ldL3Jlc3VsdF90aW1lc1swXSk7CiAgfSAKICBwcmludGYo
Im1lYW46ICAgICU1LjJmc2VjICAgICU1LjJmTSAgICAgICAgICUuMmZcbiIsCgkgZXhwKGdtZWFu
X3RpbWVzL2N1cnJlbnRfdGVzdCksCgkgZXhwKGdtZWFuX3JhdGUvY3VycmVudF90ZXN0KSwKCSBl
eHAoZ21lYW5fcmF0aW8vY3VycmVudF90ZXN0KSk7CiAgcHJpbnRmKCJcblRvdGFsIGFic29sdXRl
IHRpbWU6ICUuMmYgc2VjXG4iLCB0b3RhbF9hYnNvbHV0ZV90aW1lcyk7ICAvLyBzYW0gYWRkZWQg
MTIvMDUvOTUKICBwcmludGYoIlxuQWJzdHJhY3Rpb24gUGVuYWx0eTogJS4yZlxuXG4iLCBleHAo
Z21lYW5fcmF0aW8vY3VycmVudF90ZXN0KSk7Cn0KCmNsb2NrX3Qgc3RhcnRfdGltZSwgZW5kX3Rp
bWU7CgppbmxpbmUgdm9pZCBzdGFydF90aW1lcigpIHsgc3RhcnRfdGltZSA9IGNsb2NrKCk7IH0K
CmlubGluZSBkb3VibGUgdGltZXIoKSB7CiAgZW5kX3RpbWUgPSBjbG9jaygpOwogIHJldHVybiAo
ZW5kX3RpbWUgLSBzdGFydF90aW1lKS9kb3VibGUoQ0xPQ0tTX1BFUl9TRUMpOwp9Cgpjb25zdCBk
b3VibGUgaW5pdF92YWx1ZSA9IDMuOwoKCgpkb3VibGUgZGF0YVtTSVpFXTsKCkRvdWJsZSBEYXRh
W1NJWkVdOwoKaW5saW5lIHZvaWQgY2hlY2soZG91YmxlIHJlc3VsdCkgewogIGlmIChyZXN1bHQg
IT0gU0laRSAqIGluaXRfdmFsdWUpIHByaW50ZigidGVzdCAlaSBmYWlsZWRcbiIsIGN1cnJlbnRf
dGVzdCk7Cn0KCnZvaWQgdGVzdDAoZG91YmxlKiBmaXJzdCwgZG91YmxlKiBsYXN0KSB7CiAgc3Rh
cnRfdGltZXIoKTsKICBmb3IoaW50IGkgPSAwOyBpIDwgaXRlcmF0aW9uczsgKytpKSB7CiAgICBk
b3VibGUgcmVzdWx0ID0gMDsKICAgIGZvciAoaW50IG4gPSAwOyBuIDwgbGFzdCAtIGZpcnN0OyAr
K24pIHJlc3VsdCArPSBmaXJzdFtuXTsKICAgIGNoZWNrKHJlc3VsdCk7CiAgfQogIHJlc3VsdF90
aW1lc1tjdXJyZW50X3Rlc3QrK10gPSB0aW1lcigpOwp9CgoKdGVtcGxhdGUgPGNsYXNzIEl0ZXJh
dG9yLCBjbGFzcyBUPgp2b2lkIHRlc3QoSXRlcmF0b3IgZmlyc3QsIEl0ZXJhdG9yIGxhc3QsIFQg
emVybykgewogIGludCBpOwogIHN0YXJ0X3RpbWVyKCk7CiAgZm9yKGkgPSAwOyBpIDwgaXRlcmF0
aW9uczsgKytpKQogICAgY2hlY2soZG91YmxlKGFjY3VtdWxhdGUoZmlyc3QsIGxhc3QsIHplcm8p
KSk7CiAgcmVzdWx0X3RpbWVzW2N1cnJlbnRfdGVzdCsrXSA9IHRpbWVyKCk7Cn0KCnRlbXBsYXRl
IDxjbGFzcyBJdGVyYXRvciwgY2xhc3MgVD4Kdm9pZCBmaWxsKEl0ZXJhdG9yIGZpcnN0LCBJdGVy
YXRvciBsYXN0LCBUIHZhbHVlKSB7CiAgd2hpbGUgKGZpcnN0ICE9IGxhc3QpICpmaXJzdCsrID0g
dmFsdWU7Cn0KCgpkb3VibGUgZCA9IDAuOwpEb3VibGUgRCA9IDAuOwp0eXBlZGVmIGRvdWJsZSog
ZHA7CmRwIGRwYiA9IGRhdGE7CmRwIGRwZSA9IGRhdGEgKyBTSVpFOwp0eXBlZGVmIERvdWJsZSog
RHA7CkRwIERwYiA9IERhdGE7CkRwIERwZSA9IERhdGEgKyBTSVpFOwp0eXBlZGVmIGRvdWJsZV9w
b2ludGVyIGRQOwpkUCBkUGIoZHBiKTsKZFAgZFBlKGRwZSk7CnR5cGVkZWYgRG91YmxlX3BvaW50
ZXIgRFA7CkRQIERQYihEcGIpOwpEUCBEUGUoRHBlKTsKdHlwZWRlZiByZXZlcnNlX2l0ZXJhdG9y
PGRwLCBkb3VibGU+IHJkcDsKcmRwIHJkcGIoZHBlKTsKcmRwIHJkcGUoZHBiKTsKdHlwZWRlZiBy
ZXZlcnNlX2l0ZXJhdG9yPERwLCBEb3VibGU+IHJEcDsKckRwIHJEcGIoRHBlKTsKckRwIHJEcGUo
RHBiKTsKdHlwZWRlZiByZXZlcnNlX2l0ZXJhdG9yPGRQLCBkb3VibGU+IHJkUDsKcmRQIHJkUGIo
ZFBlKTsKcmRQIHJkUGUoZFBiKTsKdHlwZWRlZiByZXZlcnNlX2l0ZXJhdG9yPERQLCBEb3VibGU+
IHJEUDsKckRQIHJEUGIoRFBlKTsKckRQIHJEUGUoRFBiKTsKdHlwZWRlZiByZXZlcnNlX2l0ZXJh
dG9yPHJkcCwgZG91YmxlPiBycmRwOwpycmRwIHJyZHBiKHJkcGUpOwpycmRwIHJyZHBlKHJkcGIp
Owp0eXBlZGVmIHJldmVyc2VfaXRlcmF0b3I8ckRwLCBEb3VibGU+IHJyRHA7CnJyRHAgcnJEcGIo
ckRwZSk7CnJyRHAgcnJEcGUockRwYik7CnR5cGVkZWYgcmV2ZXJzZV9pdGVyYXRvcjxyZFAsIGRv
dWJsZT4gcnJkUDsKcnJkUCBycmRQYihyZFBlKTsKcnJkUCBycmRQZShyZFBiKTsKdHlwZWRlZiBy
ZXZlcnNlX2l0ZXJhdG9yPHJEUCwgRG91YmxlPiByckRQOwpyckRQIHJyRFBiKHJEUGUpOwpyckRQ
IHJyRFBlKHJEUGIpOwoKaW50IG1haW4oaW50IGFyZ3YsIGNoYXIqKiBhcmdjKSB7CiAgaWYgKGFy
Z3YgPiAxKSBpdGVyYXRpb25zID0gYXRvaShhcmdjWzFdKTsKICBmaWxsKGRwYiwgZHBlLCBkb3Vi
bGUoaW5pdF92YWx1ZSkpOwogIGZpbGwoRHBiLCBEcGUsIERvdWJsZShpbml0X3ZhbHVlKSk7CiAg
dGVzdDAoZHBiLCBkcGUpOwogIHRlc3QoZHBiLCBkcGUsIGQpOwogIHRlc3QoRHBiLCBEcGUsIEQp
OwogIHRlc3QoZFBiLCBkUGUsIGQpOwogIHRlc3QoRFBiLCBEUGUsIEQpOwogIHRlc3QocmRwYiwg
cmRwZSwgZCk7CiAgdGVzdChyRHBiLCByRHBlLCBEKTsKICB0ZXN0KHJkUGIsIHJkUGUsIGQpOwog
IHRlc3QockRQYiwgckRQZSwgRCk7CiAgdGVzdChycmRwYiwgcnJkcGUsIGQpOwogIHRlc3QocnJE
cGIsIHJyRHBlLCBEKTsKICB0ZXN0KHJyZFBiLCBycmRQZSwgZCk7CiAgdGVzdChyckRQYiwgcnJE
UGUsIEQpOwogIHN1bW1hcml6ZSgpOwogIHJldHVybiAwOwp9CgoKCg==