[Python-Dev] I think my set module is ready for prime time; comments?

Jeremy Hylton jeremy@alum.mit.edu
Tue, 23 Jan 2001 13:41:23 -0500 (EST) 

--OvJPdPv5cJ
Content-Type: text/plain; charset=us-ascii
Content-Description: message body text
Content-Transfer-Encoding: 7bit

>>>>> "ESR" == Eric S Raymond <esr@thyrsus.com> writes:

  ESR> Guido van Rossum <guido@digicool.com>:
  >> Having just skimmed your docs, I'm disappointed that you choose
  >> lists as your fundamental representation type -- this makes it
  >> slow to test for membership and hence makes intersection and
  >> union slow.

  ESR> Not quite.  Membership test is still linear-time; so is adding
  ESR> and deleting elements.  It's true that union and intersection
  ESR> are quadratic, but see below.

  >> I suppose that you have evidence from using this that those
  >> operations aren't used much, or not for large sets?

  ESR> Exactly!  In my experience the usage pattern of a class like
  ESR> this runs heavily to small sets (usually < 64 elements);
  ESR> membership tests dominate usage, with addition and deletion of
  ESR> elements running second and the "classical" boolean operations
  ESR> like union and intersection being uncommon.

I use a Set type in the compiler package (Tools/compiler/compiler) to
collect the names for a code block.  I implemented a trivial Set type
using a dictionary, because it supported the operations I was most
interested in: addition, membership tests, intersection, and get
elements as sequence (in arbitrary order).  Those are the only
operations the compiler uses.

I think I use sets for this purpose frequently, although I can't think
of any other good examples at the moment.  I usually just use a
dictionary explicitly.  In the compiler, I chose an explicit Set class
with unique method names (add, has_elt, elements) to make it obvious
for readers that I was using a set.

  ESR> What you get by going with a dictionary representation is that
  ESR> membership test becomes close to constant-time, while insertion
  ESR> and deletion become sometimes cheap and sometimes quite
  ESR> expensive (depending of course on whether you have to allocate
  ESR> a new hash bucket).  Given the usage pattern I described, the
  ESR> overall difference in performance is marginal.

The cost of insertion would presumably be dominated by the frequency
of dictionary resizes.  I don't know how often they occur, but I
assume the dictionary type is designed to accommodate efficient
insert.

I did a quick and dirty performance comparison of dictionary-based and
list-based sets.  (I'll include the code below.)  It uses sample data
collected from running the compiler; so it is measuring actual usage.

The tests showed that dictionary-based sets were always faster.  For
small tests (3 operations), the difference was about 10 percent.  For
larger tests (88 operations), the difference ranged from 180 to almost
700 percent.

  >> This is one of the problems with coming up with a set type for
  >> the core: it has to work for (nearly) everybody.

  ESR> As I pointed out above (and someone else on the list had made
  ESR> the same point earlier), "works for everbody" isn't really
  ESR> possible here.  So my solution does the next best thing -- pick
  ESR> a choice of tradeoffs that isn't obviously worse than the
  ESR> alternatives and keeps things bog-simple.

For my applications, the dictionary-based approach is faster and
offers a natural interface.  If a set implementation were included in
the standard library, I would like to see either (1) the
implementation that favors my needs <wink> or (2) multiple
implementations tuned for different uses.  I think it would be just as
easy to make set implementations available separately, though.

Jeremy


--OvJPdPv5cJ
Content-Type: text/plain
Content-Disposition: inline;
	filename="sets.tar"
Content-Transfer-Encoding: base64

c2V0cy8AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAADAwNDA3NzUA
MDAwMTU1NgAwMDAwNzY1ADAwMDAwMDAwMDAwADA3MjMzMzUwMDA1ADAxMTIxNQAgNQAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB1c3RhciAgAGplcmVt
eQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAYWRtaW4AAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABzZXRzL3Rlc3RzZXQxOC5weQAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAMDEwMDY2NAAwMDAxNTU2ADAwMDA3NjUAMDAwMDAwMDQ2MTQA
MDcyMzMzNDcyNDMAMDEzNDQ3ACAwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAHVzdGFyICAAamVyZW15AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABh
ZG1pbgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAHNp
emUgPSA4OA0KDQpkZWYgdGVzdChmYWN0b3J5KToNCiAgICBzZXQgPSBmYWN0b3J5KCkNCiAg
ICBzZXQuYWRkKCdvcHRpbWl6ZWQnKQ0KICAgIHNldC5hZGQoJ19faW5pdF9fJykNCiAgICBz
ZXQuYWRkKCdfc2V0dXBHcmFwaERlbGVnYXRpb24nKQ0KICAgIHNldC5hZGQoJ2dldENvZGUn
KQ0KICAgIHNldC5hZGQoJ2lzTG9jYWxOYW1lJykNCiAgICBzZXQuYWRkKCdzdG9yZU5hbWUn
KQ0KICAgIHNldC5hZGQoJ2xvYWROYW1lJykNCiAgICBzZXQuYWRkKCdkZWxOYW1lJykNCiAg
ICBzZXQuYWRkKCdfbmFtZU9wJykNCiAgICBzZXQuYWRkKCdzZXRfbGluZW5vJykNCiAgICBz
ZXQuYWRkKCd2aXNpdE1vZHVsZScpDQogICAgc2V0LmFkZCgndmlzaXRGdW5jdGlvbicpDQog
ICAgc2V0LmFkZCgndmlzaXRMYW1iZGEnKQ0KICAgIHNldC5hZGQoJ192aXNpdEZ1bmNPckxh
bWJkYScpDQogICAgc2V0LmFkZCgndmlzaXRDbGFzcycpDQogICAgc2V0LmFkZCgndmlzaXRJ
ZicpDQogICAgc2V0LmFkZCgndmlzaXRXaGlsZScpDQogICAgc2V0LmFkZCgndmlzaXRGb3In
KQ0KICAgIHNldC5hZGQoJ3Zpc2l0QnJlYWsnKQ0KICAgIHNldC5hZGQoJ3Zpc2l0Q29udGlu
dWUnKQ0KICAgIHNldC5hZGQoJ3Zpc2l0VGVzdCcpDQogICAgc2V0LmFkZCgndmlzaXRBbmQn
KQ0KICAgIHNldC5hZGQoJ3Zpc2l0T3InKQ0KICAgIHNldC5hZGQoJ3Zpc2l0Q29tcGFyZScp
DQogICAgc2V0LmFkZCgnX19saXN0X2NvdW50JykNCiAgICBzZXQuYWRkKCd2aXNpdExpc3RD
b21wJykNCiAgICBzZXQuYWRkKCd2aXNpdExpc3RDb21wRm9yJykNCiAgICBzZXQuYWRkKCd2
aXNpdExpc3RDb21wSWYnKQ0KICAgIHNldC5hZGQoJ3Zpc2l0QXNzZXJ0JykNCiAgICBzZXQu
YWRkKCd2aXNpdFJhaXNlJykNCiAgICBzZXQuYWRkKCd2aXNpdFRyeUV4Y2VwdCcpDQogICAg
c2V0LmFkZCgndmlzaXRUcnlGaW5hbGx5JykNCiAgICBzZXQuYWRkKCd2aXNpdERpc2NhcmQn
KQ0KICAgIHNldC5hZGQoJ3Zpc2l0Q29uc3QnKQ0KICAgIHNldC5hZGQoJ3Zpc2l0S2V5d29y
ZCcpDQogICAgc2V0LmFkZCgndmlzaXRHbG9iYWwnKQ0KICAgIHNldC5hZGQoJ3Zpc2l0TmFt
ZScpDQogICAgc2V0LmFkZCgndmlzaXRQYXNzJykNCiAgICBzZXQuYWRkKCd2aXNpdEltcG9y
dCcpDQogICAgc2V0LmFkZCgndmlzaXRGcm9tJykNCiAgICBzZXQuYWRkKCdfcmVzb2x2ZURv
dHMnKQ0KICAgIHNldC5hZGQoJ3Zpc2l0R2V0YXR0cicpDQogICAgc2V0LmFkZCgndmlzaXRB
c3NpZ24nKQ0KICAgIHNldC5hZGQoJ3Zpc2l0QXNzTmFtZScpDQogICAgc2V0LmFkZCgndmlz
aXRBc3NBdHRyJykNCiAgICBzZXQuYWRkKCdfdmlzaXRBc3NTZXF1ZW5jZScpDQogICAgc2V0
LmFkZCgndmlzaXRBc3NUdXBsZScpDQogICAgc2V0LmFkZCgndmlzaXRBc3NMaXN0JykNCiAg
ICBzZXQuYWRkKCd2aXNpdEFzc1R1cGxlJykNCiAgICBzZXQuYWRkKCd2aXNpdEFzc0xpc3Qn
KQ0KICAgIHNldC5hZGQoJ3Zpc2l0QXVnQXNzaWduJykNCiAgICBzZXQuYWRkKCdfYXVnbWVu
dGVkX29wY29kZScpDQogICAgc2V0LmFkZCgndmlzaXRBdWdOYW1lJykNCiAgICBzZXQuYWRk
KCd2aXNpdEF1Z0dldGF0dHInKQ0KICAgIHNldC5hZGQoJ3Zpc2l0QXVnU2xpY2UnKQ0KICAg
IHNldC5hZGQoJ3Zpc2l0QXVnU3Vic2NyaXB0JykNCiAgICBzZXQuYWRkKCd2aXNpdEV4ZWMn
KQ0KICAgIHNldC5hZGQoJ3Zpc2l0Q2FsbEZ1bmMnKQ0KICAgIHNldC5hZGQoJ3Zpc2l0UHJp
bnQnKQ0KICAgIHNldC5hZGQoJ3Zpc2l0UHJpbnRubCcpDQogICAgc2V0LmFkZCgndmlzaXRS
ZXR1cm4nKQ0KICAgIHNldC5hZGQoJ3Zpc2l0U2xpY2UnKQ0KICAgIHNldC5hZGQoJ3Zpc2l0
U3Vic2NyaXB0JykNCiAgICBzZXQuYWRkKCdiaW5hcnlPcCcpDQogICAgc2V0LmFkZCgndmlz
aXRBZGQnKQ0KICAgIHNldC5hZGQoJ3Zpc2l0U3ViJykNCiAgICBzZXQuYWRkKCd2aXNpdE11
bCcpDQogICAgc2V0LmFkZCgndmlzaXREaXYnKQ0KICAgIHNldC5hZGQoJ3Zpc2l0TW9kJykN
CiAgICBzZXQuYWRkKCd2aXNpdFBvd2VyJykNCiAgICBzZXQuYWRkKCd2aXNpdExlZnRTaGlm
dCcpDQogICAgc2V0LmFkZCgndmlzaXRSaWdodFNoaWZ0JykNCiAgICBzZXQuYWRkKCd1bmFy
eU9wJykNCiAgICBzZXQuYWRkKCd2aXNpdEludmVydCcpDQogICAgc2V0LmFkZCgndmlzaXRV
bmFyeVN1YicpDQogICAgc2V0LmFkZCgndmlzaXRVbmFyeUFkZCcpDQogICAgc2V0LmFkZCgn
dmlzaXRVbmFyeUludmVydCcpDQogICAgc2V0LmFkZCgndmlzaXROb3QnKQ0KICAgIHNldC5h
ZGQoJ3Zpc2l0QmFja3F1b3RlJykNCiAgICBzZXQuYWRkKCdiaXRPcCcpDQogICAgc2V0LmFk
ZCgndmlzaXRCaXRhbmQnKQ0KICAgIHNldC5hZGQoJ3Zpc2l0Qml0b3InKQ0KICAgIHNldC5h
ZGQoJ3Zpc2l0Qml0eG9yJykNCiAgICBzZXQuYWRkKCd2aXNpdEVsbGlwc2lzJykNCiAgICBz
ZXQuYWRkKCd2aXNpdFR1cGxlJykNCiAgICBzZXQuYWRkKCd2aXNpdExpc3QnKQ0KICAgIHNl
dC5hZGQoJ3Zpc2l0U2xpY2VvYmonKQ0KICAgIHNldC5hZGQoJ3Zpc2l0RGljdCcpDQoAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAHNldHMvdGVzdHNldDg4LnB5AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAwMTAw
NjY0ADAwMDE1NTYAMDAwMDc2NQAwMDAwMDAwMDUzNAAwNzIzMzM0NzI0MwAwMTM0NTMAIDAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAdXN0YXIgIABq
ZXJlbXkAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAGFkbWluAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAc2l6ZSA9IDEzDQoNCmRlZiB0ZXN0KGZh
Y3RvcnkpOg0KICAgIHNldCA9IGZhY3RvcnkoKQ0KICAgIHNldC5hZGQoJ3NlbGYnKQ0KICAg
IHNldC5hZGQoJ2V4cHInKQ0KICAgIHNldC5hZGQoJ2ZsYWdzJykNCiAgICBzZXQuYWRkKCds
b3dlcicpDQogICAgc2V0LmFkZCgndXBwZXInKQ0KICAgIHNldC5oYXNfZWx0KCdleHByJykN
CiAgICBzZXQuaGFzX2VsdCgnc2VsZicpDQogICAgc2V0Lmhhc19lbHQoJ2ZsYWdzJykNCiAg
ICBzZXQuaGFzX2VsdCgnc2VsZicpDQogICAgc2V0Lmhhc19lbHQoJ2xvd2VyJykNCiAgICBz
ZXQuaGFzX2VsdCgnc2VsZicpDQogICAgc2V0Lmhhc19lbHQoJ3VwcGVyJykNCiAgICBzZXQu
aGFzX2VsdCgnc2VsZicpDQoAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAHNldHMvdGVzdHNldDk4LnB5AAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAwMTAwNjY0ADAwMDE1NTYAMDAwMDc2NQAwMDAwMDAwMDE3NQAwNzIzMzM0
NzI0MwAwMTM0NTUAIDAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAdXN0YXIgIABqZXJlbXkAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAGFkbWluAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAc2l6ZSA9IDMN
Cg0KZGVmIHRlc3QoZmFjdG9yeSk6DQogICAgc2V0ID0gZmFjdG9yeSgpDQogICAgc2V0LmFk
ZCgnX19pbml0X18nKQ0KICAgIHNldC5hZGQoJ19nZXRDaGlsZHJlbicpDQogICAgc2V0LmFk
ZCgnX19yZXByX18nKQ0KAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAc2V0cy90aW1lc2V0LnB5AAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAADAxMDA2NjQAMDAwMTU1NgAwMDAwNzY1ADAwMDAwMDAxNDczADA3
MjMzMzQ3NjE0ADAxMzI1NwAgMAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAB1c3RhciAgAGplcmVteQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAYWRt
aW4AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABpbXBv
cnQgZXNyc2V0DQppbXBvcnQgamFoc2V0DQppbXBvcnQgb3MNCmltcG9ydCB0aW1lDQoNCmRl
ZiB0aW1laXQoZiwgaXRlcnM9cmFuZ2UoMzAwMCkpOg0KICAgIHQwID0gdGltZS5jbG9jaygp
DQogICAgZm9yIGkgaW4gaXRlcnM6DQogICAgICAgIGYoKQ0KICAgIHQxID0gdGltZS5jbG9j
aygpDQogICAgcmV0dXJuIHQxIC0gdDANCg0KY2xhc3MgZXNyd3JhcChlc3JzZXQuc2V0KToN
CiAgICBkZWYgX19pbml0X18oc2VsZik6DQogICAgICAgIHNlbGYuZWxlbWVudHMgPSBbXQ0K
DQogICAgYWRkID0gZXNyc2V0LnNldC5hcHBlbmQNCg0KICAgIGRlZiBoYXNfZWx0KHNlbGYs
IGVsdCk6DQogICAgICAgIHJldHVybiBlbHQgaW4gc2VsZi5lbGVtZW50cw0KDQogICAgZGVm
IHJlbW92ZShzZWxmLCBlbHQpOg0KICAgICAgICBpID0gc2VsZi5pbmRleChlbHQpDQogICAg
ICAgIGRlbCBzZWxmLmVsZW1lbnRzW2ldDQoNCmRlZiBsaXN0X3Rlc3QoKToNCiAgICBtb2R1
bGUudGVzdChlc3J3cmFwKQ0KDQpkZWYgZGljdF90ZXN0KCk6DQogICAgbW9kdWxlLnRlc3Qo
amFoc2V0LlNldCkNCg0KZm9yIGZpbGUgaW4gb3MubGlzdGRpcigiLiIpOg0KICAgIGlmIG5v
dCBmaWxlLnN0YXJ0c3dpdGgoJ3Rlc3RzZXQnKToNCiAgICAgICAgY29udGludWUNCiAgICBu
YW1lLCBleHQgPSBvcy5wYXRoLnNwbGl0ZXh0KGZpbGUpDQogICAgaWYgZXh0ICE9ICcucHkn
Og0KICAgICAgICBjb250aW51ZQ0KICAgIG1vZHVsZSA9IF9faW1wb3J0X18obmFtZSkNCg0K
ICAgIHByaW50IG5hbWUsIG1vZHVsZS5zaXplDQogICAgcHJpbnQgImRpY3QiLCB0aW1laXQo
ZGljdF90ZXN0KSwgImxpc3QiLCB0aW1laXQobGlzdF90ZXN0KQ0KICAgIHByaW50DQogICAg
DQoAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAHNldHMvZXNyc2V0LnB5AAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAwMTAwNjY0ADAwMDE1NTYAMDAwMDc2NQAw
MDAwMDAxMzA0MgAwNzIzMzM0NzI1MwAwMTMxMDQAIDAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAdXN0YXIgIABqZXJlbXkAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAGFkbWluAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAIyBEZXNpZ24gYW5kIGltcGxlbWVudGF0aW9uIGJ5IEVTUiwgSmFudWFyeSAy
MDAxLg0KDQpkZWYgc2V0aWZ5KGxpc3QxKToJCSMgVXNlZCBieSBzZXQgY29uc3RydWN0b3IN
CiAgICAiUmVtb3ZlIGR1cGxpY2F0ZXMgaW4gc2VxdWVuY2UuIg0KICAgIHJlcyA9IFtdDQog
ICAgZm9yIGkgaW4gcmFuZ2UobGVuKGxpc3QxKSk6DQoJZHVwbGljYXRlID0gMA0KICAgICAg
ICBmb3IgaiBpbiByYW5nZShpKToNCgkgICAgaWYgbGlzdDFbaV0gPT0gbGlzdDFbal06DQoJ
CWR1cGxpY2F0ZSA9IDENCgkJYnJlYWsNCglpZiBub3QgZHVwbGljYXRlOg0KCSAgICByZXMu
YXBwZW5kKGxpc3QxW2ldKQ0KICAgIHJldHVybiByZXMNCg0KZGVmIHVuaW9uKGxpc3QxLCBs
aXN0Mik6CQkjIFVzZWQgZm9yIHwNCiAgICAiQ29tcHV0ZSBzZXQgaW50ZXJzZWN0aW9uIG9m
IHNlcXVlbmNlcy4iDQogICAgcmVzID0gbGlzdDFbOl0NCiAgICBmb3IgeCBpbiBsaXN0MjoN
CglpZiBub3QgeCBpbiBsaXN0MToNCgkgICAgcmVzLmFwcGVuZCh4KQ0KICAgIHJldHVybiBy
ZXMNCg0KZGVmIGludGVyc2VjdGlvbihsaXN0MSwgbGlzdDIpOgkJIyBVc2VkIGZvciAmDQog
ICAgIkNvbXB1dGUgc2V0IGludGVyc2VjdGlvbiBvZiBzZXF1ZW5jZXMuIg0KICAgIHJlcyA9
IFtdDQogICAgZm9yIHggaW4gbGlzdDE6DQoJaWYgeCBpbiBsaXN0MjoNCgkgICAgcmVzLmFw
cGVuZCh4KQ0KICAgIHJldHVybiByZXMNCg0KZGVmIGRpZmZlcmVuY2UobGlzdDEsIGxpc3Qy
KToJCSMgVXNlZCBmb3IgLQ0KICAgICJDb21wdXRlIHNldCBkaWZmZXJlbmNlIG9mIHNlcXVl
bmNlcy4iDQogICAgcmVzID0gW10NCiAgICBmb3IgeCBpbiBsaXN0MToNCglpZiBub3QgeCBp
biBsaXN0MjoNCgkgICAgcmVzLmFwcGVuZCh4KQ0KICAgIHJldHVybiByZXMNCg0KZGVmIHN5
bW1ldHJpY19kaWZmZXJlbmNlKGxpc3QxLCBsaXN0Mik6CSMgVXNlZCBmb3IgXg0KICAgICJD
b21wdXRlIHNldCBzeW1tZXRyaWMtZGlmZmVyZW5jZSBvZiBzZXF1ZW5jZXMuIg0KICAgIHJl
cyA9IFtdDQogICAgZm9yIHggaW4gbGlzdDE6DQoJaWYgbm90IHggaW4gbGlzdDI6DQoJICAg
IHJlcy5hcHBlbmQoeCkNCiAgICBmb3IgeCBpbiBsaXN0MjoNCglpZiBub3QgeCBpbiBsaXN0
MToNCgkgICAgcmVzLmFwcGVuZCh4KQ0KICAgIHJldHVybiByZXMNCg0KZGVmIGNhcnRlc2lh
bihsaXN0MSwgbGlzdDIpOgkJIyBVc2VkIGZvciAqDQogICAgIkNhcnRlc2lhbiBwcm9kdWN0
IG9mIHNlcXVlbmNlcyBjb25zaWRlcmVkIGFzIHNldHMuIg0KICAgIHJlcyA9IFtdDQogICAg
Zm9yIHggaW4gbGlzdDE6DQoJZm9yIHkgaW4gbGlzdDI6DQoJICAgIHJlcy5hcHBlbmQoKHgs
eSkpDQogICAgcmV0dXJuIHJlcw0KDQpkZWYgZXF1YWxpdHkobGlzdDEsIGxpc3QyKToNCiAg
ICAiVGVzdCBzZXF1ZW5jZXMgY29uc2lkZXJlZCBhcyBzZXRzIGZvciBlcXVhbGl0eS4iDQog
ICAgaWYgbGVuKGxpc3QxKSAhPSBsZW4obGlzdDIpOg0KICAgICAgICByZXR1cm4gMA0KICAg
IGZvciB4IGluIGxpc3QxOg0KICAgICAgICBpZiBub3QgeCBpbiBsaXN0MjoNCiAgICAgICAg
ICAgIHJldHVybiAwDQogICAgZm9yIHggaW4gbGlzdDI6DQogICAgICAgIGlmIG5vdCB4IGlu
IGxpc3QxOg0KICAgICAgICAgICAgcmV0dXJuIDANCiAgICByZXR1cm4gMQ0KDQpkZWYgcHJv
cGVyX3N1YnNldChsaXN0MSwgbGlzdDIpOg0KICAgICJSZXR1cm4gMSBpZiBmaXJzdCBhcmd1
bWVudCBpcyBhIHByb3BlciBzdWJzZXQgb2Ygc2Vjb25kLCAwIG90aGVyd2lzZS4iDQogICAg
aWYgbm90IGxlbihsaXN0MSkgPCBsZW4obGlzdDIpOg0KICAgICAgICByZXR1cm4gMA0KICAg
IGZvciB4IGluIGxpc3QxOg0KICAgICAgICBpZiBub3QgeCBpbiBsaXN0MjoNCiAgICAgICAg
ICAgIHJldHVybiAwDQogICAgcmV0dXJuIDENCg0KZGVmIHN1YnNldChsaXN0MSwgbGlzdDIp
Og0KICAgICJSZXR1cm4gMSBpZiBmaXJzdCBhcmd1bWVudCBpcyBhIHN1YnNldCBvZiBzZWNv
bmQsIDAgb3RoZXJ3aXNlLiINCiAgICBpZiBub3QgbGVuKGxpc3QxKSA8PSBsZW4obGlzdDIp
Og0KICAgICAgICByZXR1cm4gMA0KICAgIGZvciB4IGluIGxpc3QxOg0KICAgICAgICBpZiBu
b3QgeCBpbiBsaXN0MjoNCiAgICAgICAgICAgIHJldHVybiAwDQogICAgcmV0dXJuIDENCg0K
ZGVmIHBvd2Vyc2V0KGJhc2UpOg0KICAgICJDb21wdXRlIHRoZSBzZXQgb2YgYWxsIHN1YnNl
dHMgb2YgYSBzZXQuIg0KICAgIHBvd2Vyc2V0ID0gW10NCiAgICBmb3IgbiBpbiB4cmFuZ2Uo
MiAqKiBsZW4oYmFzZSkpOg0KCXN1YnNldCA9IFtdDQoJZm9yIGUgaW4geHJhbmdlKGxlbihi
YXNlKSk6DQoJICAgICBpZiBuICYgMiAqKiBlOg0KCQlzdWJzZXQuYXBwZW5kKGJhc2VbZV0p
DQoJcG93ZXJzZXQuYXBwZW5kKHN1YnNldCkNCiAgICByZXR1cm4gcG93ZXJzZXQNCg0KY2xh
c3Mgc2V0Og0KICAgICJMaXN0cyB3aXRoIHNldC10aGVvcmV0aWMgb3BlcmF0aW9ucy4iDQoN
CiAgICBkZWYgX19pbml0X18oc2VsZiwgdmFsdWUpOg0KICAgICAgICBzZWxmLmVsZW1lbnRz
ID0gc2V0aWZ5KHZhbHVlKQ0KDQogICAgZGVmIF9fbGVuX18oc2VsZik6DQoJcmV0dXJuIGxl
bihzZWxmLmVsZW1lbnRzKQ0KDQogICAgZGVmIF9fZ2V0aXRlbV9fKHNlbGYsIGluZCk6DQoJ
cmV0dXJuIHNlbGYuZWxlbWVudHNbaW5kXQ0KDQogICAgZGVmIF9fc2V0aXRlbV9fKHNlbGYs
IGluZCwgdmFsKToNCiAgICAgICAgaWYgdmFsIG5vdCBpbiBzZWxmLmVsZW1lbnRzOg0KICAg
ICAgICAgICAgc2VsZi5lbGVtZW50c1tpbmRdID0gdmFsDQoNCiAgICBkZWYgX19kZWxpdGVt
X18oc2VsZiwgaW5kKToNCglkZWwgc2VsZi5lbGVtZW50c1tpbmRdDQoNCiAgICBkZWYgbGlz
dChzZWxmKToNCiAgICAgICAgcmV0dXJuIHNlbGYuZWxlbWVudHMNCg0KICAgIGRlZiBhcHBl
bmQoc2VsZiwgbmV3KToNCiAgICAgICAgaWYgbmV3IG5vdCBpbiBzZWxmLmVsZW1lbnRzOg0K
ICAgICAgICAgICAgc2VsZi5lbGVtZW50cy5hcHBlbmQobmV3KQ0KDQogICAgZGVmIGV4dGVu
ZChzZWxmLCBuZXcpOg0KCXNlbGYuZWxlbWVudHMuZXh0ZW5kKG5ldykNCiAgICAgICAgc2Vs
Zi5lbGVtZW50cyA9IHNldGlmeShzZWxmLmVsZW1lbnRzKQ0KDQogICAgZGVmIGNvdW50KHNl
bGYsIHgpOg0KCXNlbGYuZWxlbWVudHMuY291bnQoeCkNCg0KICAgIGRlZiBpbmRleChzZWxm
LCB4KToNCglzZWxmLmVsZW1lbnRzLmluZGV4KHgpDQoNCiAgICBkZWYgaW5zZXJ0KHNlbGYs
IGksIHgpOg0KICAgICAgICBpZiB4IG5vdCBpbiBzZWxmLmVsZW1lbnRzOg0KICAgICAgICAg
ICAgc2VsZi5lbGVtZW50cy5pbmRleChpLCB4KQ0KDQogICAgZGVmIHBvcChzZWxmLCBpPU5v
bmUpOg0KCXNlbGYuZWxlbWVudHMucG9wKGkpDQoNCiAgICBkZWYgcmVtb3ZlKHNlbGYsIHgp
Og0KCXNlbGYuZWxlbWVudHMucmVtb3ZlKHgpDQoNCiAgICBkZWYgcmV2ZXJzZShzZWxmKToN
CglzZWxmLmVsZW1lbnRzLnJldmVyc2UoKQ0KDQogICAgZGVmIHNvcnQoc2VsZiwgY21wPU5v
bmUpOg0KCXNlbGYuZWxlbWVudHMuc29ydChjbXApDQoNCiAgICBkZWYgX19vcl9fKHNlbGYs
IG90aGVyKToNCglpZiB0eXBlKG90aGVyKSA9PSB0eXBlKHNlbGYpOg0KCSAgICBvdGhlciA9
IG90aGVyLmVsZW1lbnRzDQogICAgICAgIHJldHVybiBzZXQodW5pb24oc2VsZi5lbGVtZW50
cywgb3RoZXIpKQ0KDQogICAgX19hZGRfXyA9IF9fb3JfXw0KDQogICAgZGVmIF9fYW5kX18o
c2VsZiwgb3RoZXIpOg0KCWlmIHR5cGUob3RoZXIpID09IHR5cGUoc2VsZik6DQoJICAgIG90
aGVyID0gb3RoZXIuZWxlbWVudHMNCiAgICAgICAgcmV0dXJuIHNldChpbnRlcnNlY3Rpb24o
c2VsZi5lbGVtZW50cywgb3RoZXIpKQ0KDQogICAgZGVmIF9fc3ViX18oc2VsZiwgb3RoZXIp
Og0KCWlmIHR5cGUob3RoZXIpID09IHR5cGUoc2VsZik6DQoJICAgIG90aGVyID0gb3RoZXIu
ZWxlbWVudHMNCiAgICAgICAgcmV0dXJuIHNldChkaWZmZXJlbmNlKHNlbGYuZWxlbWVudHMs
IG90aGVyKSkNCg0KICAgIGRlZiBfX3hvcl9fKHNlbGYsIG90aGVyKToNCglpZiB0eXBlKG90
aGVyKSA9PSB0eXBlKHNlbGYpOg0KCSAgICBvdGhlciA9IG90aGVyLmVsZW1lbnRzDQogICAg
ICAgIHJldHVybiBzZXQoc3ltbWV0cmljX2RpZmZlcmVuY2Uoc2VsZi5lbGVtZW50cywgb3Ro
ZXIpKQ0KDQogICAgZGVmIF9fbXVsX18oc2VsZiwgb3RoZXIpOg0KCWlmIHR5cGUob3RoZXIp
ID09IHR5cGUoc2VsZik6DQoJICAgIG90aGVyID0gb3RoZXIuZWxlbWVudHMNCiAgICAgICAg
cmV0dXJuIHNldChjYXJ0ZXNpYW4oc2VsZi5lbGVtZW50cywgb3RoZXIpKQ0KDQogICAgZGVm
IF9fZXFfXyhzZWxmLCBvdGhlcik6DQoJaWYgdHlwZShvdGhlcikgPT0gdHlwZShzZWxmKToN
CgkgICAgb3RoZXIgPSBvdGhlci5lbGVtZW50cw0KICAgICAgICByZXR1cm4gc2VsZi5lbGVt
ZW50cyA9PSBvdGhlcg0KDQogICAgZGVmIF9fbmVfXyhzZWxmLCBvdGhlcik6DQoJaWYgdHlw
ZShvdGhlcikgPT0gdHlwZShzZWxmKToNCgkgICAgb3RoZXIgPSBvdGhlci5lbGVtZW50cw0K
ICAgICAgICByZXR1cm4gc2VsZi5lbGVtZW50cyAhPSBvdGhlcg0KDQogICAgZGVmIF9fbHRf
XyhzZWxmLCBvdGhlcik6DQoJaWYgdHlwZShvdGhlcikgPT0gdHlwZShzZWxmKToNCgkgICAg
b3RoZXIgPSBvdGhlci5lbGVtZW50cw0KICAgICAgICByZXR1cm4gcHJvcGVyX3N1YnNldChz
ZWxmLmVsZW1lbnRzLCBvdGhlcikNCg0KICAgIGRlZiBfX2xlX18oc2VsZiwgb3RoZXIpOg0K
CWlmIHR5cGUob3RoZXIpID09IHR5cGUoc2VsZik6DQoJICAgIG90aGVyID0gb3RoZXIuZWxl
bWVudHMNCiAgICAgICAgcmV0dXJuIHN1YnNldChzZWxmLmVsZW1lbnRzLCBvdGhlcikNCg0K
ICAgIGRlZiBfX2d0X18oc2VsZiwgb3RoZXIpOg0KCWlmIHR5cGUob3RoZXIpID09IHR5cGUo
c2VsZik6DQoJICAgIG90aGVyID0gb3RoZXIuZWxlbWVudHMNCiAgICAgICAgcmV0dXJuIHBy
b3Blcl9zdWJzZXQob3RoZXIsIHNlbGYuZWxlbWVudHMpDQoNCiAgICBkZWYgX19nZV9fKHNl
bGYsIG90aGVyKToNCglpZiB0eXBlKG90aGVyKSA9PSB0eXBlKHNlbGYpOg0KCSAgICBvdGhl
ciA9IG90aGVyLmVsZW1lbnRzDQogICAgICAgIHJldHVybiBzdWJzZXQob3RoZXIsIHNlbGYu
ZWxlbWVudHMpDQoNCiAgICBkZWYgX19zdHJfXyhzZWxmKToNCiAgICAgICAgcmVzID0gInsi
DQogICAgICAgIGZvciB4IGluIHNlbGYuZWxlbWVudHM6DQogICAgICAgICAgICByZXMgPSBy
ZXMgKyBzdHIoeCkgKyAiLCAiDQogICAgICAgIHJlcyA9IHJlc1swOi0yXSArICJ9Ig0KICAg
ICAgICByZXR1cm4gcmVzDQoNCiAgICBkZWYgX19yZXByX18oc2VsZik6DQogICAgICAgIHJl
dHVybiByZXByKHNlbGYuZWxlbWVudHMpDQoNCmlmIF9fbmFtZV9fID09ICdfX21haW5fXyc6
DQogICAgYSA9IHNldChbMSwgMiwgMywgNF0pDQogICAgYiA9IHNldChbMSwgNF0pDQogICAg
YyA9IHNldChbNSwgNl0pDQogICAgZCA9IFsxLCAxLCAyLCAxXQ0KICAgIHByaW50IGBkYCwg
InNldGlmaWVzIHRvIiwgc2V0KGQpDQogICAgcHJpbnQgYGFgLCAifCIsIGBiYCwgImlzIiwg
YGEgfCBiYA0KICAgIHByaW50IGBhYCwgIl4iLCBgYmAsICJpcyIsIGBhIF4gYmANCiAgICBw
cmludCBgYWAsICImIiwgYGJgLCAiaXMiLCBgYSAmIGJgDQogICAgcHJpbnQgYGJgLCAiKiIs
IGBjYCwgImlzIiwgYGIgKiBjYA0KICAgIHByaW50IGBhYCwgJzwnLCBgYmAsICJpcyIsIGBh
IDwgYmANCiAgICBwcmludCBgYWAsICc+JywgYGJgLCAiaXMiLCBgYSA+IGJgDQogICAgcHJp
bnQgYGJgLCAnPCcsIGBjYCwgImlzIiwgYGIgPCBjYA0KICAgIHByaW50IGBiYCwgJz4nLCBg
Y2AsICJpcyIsIGBiID4gY2ANCiAgICBwcmludCAiUG93ZXIgc2V0IG9mIiwgYGNgLCAiaXMi
LCBwb3dlcnNldChjKQ0KDQojIGVuZA0KAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAHNldHMvamFoc2V0LnB5AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAwMTAwNjY0ADAwMDE1NTYAMDAwMDc2NQAwMDAwMDAwMDYwMQAwNzIzMzM0Nzcx
NQAwMTMwNTUAIDAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAdXN0YXIgIABqZXJlbXkAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAGFkbWluAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAY2xhc3MgU2V0Og0K
ICAgIGRlZiBfX2luaXRfXyhzZWxmKToNCiAgICAgICAgc2VsZi5lbHRzID0ge30NCiMjICAg
ICAgICBzZXRzIGFyZSBmYXN0ZXIgd2hlbiBtZXRob2Qgb3ZlcmhlYWQgaXMgcmVtb3ZlZDoN
CiMjICAgICAgICBzZWxmLmVsZW1lbnRzID0gc2VsZi5lbHRzLmtleXMNCiMjICAgICAgICBz
ZWxmLmhhc19lbHQgPSBzZWxmLmVsdHMuaGFzX2tleQ0KDQogICAgZGVmIGFkZChzZWxmLCBl
bHQpOg0KICAgICAgICBzZWxmLmVsdHNbZWx0XSA9IE5vbmUNCg0KICAgIGRlZiBlbGVtZW50
cyhzZWxmKToNCiAgICAgICAgcmV0dXJuIHNlbGYuZWx0cy5rZXlzKCkNCg0KICAgIGRlZiBo
YXNfZWx0KHNlbGYsIGVsdCk6DQogICAgICAgIHJldHVybiBzZWxmLmVsdHMuaGFzX2tleShl
bHQpDQogICAgDQoAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA==

--OvJPdPv5cJ--