[PATCH] Use 128-bit math to accelerate numeric division, when 8 < divisor digits <= 16

Started by Joel Jacobsonalmost 3 years ago8 messages
#1Joel Jacobson
joel@compiler.org
2 attachment(s)

Hi,

On platforms where we support 128bit integers, we could accelerate division
when the number of digits in the divisor is larger than 8 and less than or
equal to 16 digits, i.e. when the divisor that fits in a 64-bit integer but would
not fit in a 32-bit integer.

This patch adds div_var_int64(), which is similar to the existing div_var_int(),
but accepts a 64-bit divisor instead of a 32-bit divisor.

The new function is used within div_var() and div_var_fast().

To measure the effect, we need a volatile wrapper function for numeric_div(),
to avoid it being cached since it's immutable:

CREATE OR REPLACE FUNCTION numeric_div_volatile(numeric,numeric)
RETURNS numeric LANGUAGE internal AS 'numeric_div';

We can then use generate_series() to measure the execution time for lots of
executions. This does not account for the overhead of generate_series() and
count(), but that's okay since the overhead is the same in both measurements,
so the relative difference is still correct.

--
-- Division when the divisor is 8 digits should be unchanged:
--
EXPLAIN ANALYZE
SELECT count(numeric_div_volatile(
repeat('1',131071)::numeric,
repeat('3',8)::numeric
)) FROM generate_series(1,1e4);
-- Execution Time: 1633.722 ms (HEAD)
-- Execution Time: 1680.228 ms (div_var_int64.patch)

--
-- Division when the divisor is 9 digits should be faster:
--
EXPLAIN ANALYZE
SELECT count(numeric_div_volatile(
repeat('1',131071)::numeric,
repeat('3',9)::numeric
)) FROM generate_series(1,1e4);
-- Execution Time: 5444.755 ms (HEAD)
-- Execution Time: 1604.967 ms (div_var_int64.patch)

--
-- Division when the divisor is 16 digits should also be faster:
--
EXPLAIN ANALYZE
SELECT count(numeric_div_volatile(
repeat('1',131071)::numeric,
repeat('3',16)::numeric
)) FROM generate_series(1,1e4);
-- Execution Time: 6072.683 ms (HEAD)
-- Execution Time: 3215.686 ms (div_var_int64.patch)

--
-- Division when the divisor is 17 digits should be unchanged:
--
EXPLAIN ANALYZE
SELECT count(numeric_div_volatile(
repeat('1',131071)::numeric,
repeat('3',17)::numeric
)) FROM generate_series(1,1e4);
-- Execution Time: 6948.150 ms (HEAD)
-- Execution Time: 7010.544 ms (div_var_int64.patch)

--
-- Same tests as above, but with a single digit dividend,
-- and 1e7 executions instead of just 1e4.
--

--
-- Division when the divisor is 8 digits should be unchanged:
--
EXPLAIN ANALYZE
SELECT count(numeric_div_volatile(
1,
repeat('3',8)::numeric
)) FROM generate_series(1,1e7);
-- Execution Time: 1827.567 ms (HEAD)
-- Execution Time: 1828.029 ms (div_var_int64.patch)

--
-- Division when the divisor is 9 digits should be faster:
--
EXPLAIN ANALYZE
SELECT count(numeric_div_volatile(
1,
repeat('3',9)::numeric
)) FROM generate_series(1,1e7);
-- Execution Time: 2314.851 ms (HEAD)
-- Execution Time: 1886.170 ms (div_var_int64.patch)

--
-- Division when the divisor is 16 digits should also be faster:
--
EXPLAIN ANALYZE
SELECT count(numeric_div_volatile(
1,
repeat('3',16)::numeric
)) FROM generate_series(1,1e7);
-- Execution Time: 2244.009 ms (HEAD)
-- Execution Time: 1968.148 ms (div_var_int64.patch)

--
-- Division when the divisor is 17 digits should be unchanged:
--
EXPLAIN ANALYZE
SELECT count(numeric_div_volatile(
1,
repeat('3',17)::numeric
)) FROM generate_series(1,1e7);
-- Execution Time: 2334.896 ms (HEAD)
-- Execution Time: 2338.141 ms (div_var_int64.patch)

The graph below shows the effect on execution time for numeric_div(),
and also looks at numeric_mod() since it's a heavy user of numeric_div().

The graph was produced by generating 100 random numeric integer values
for each combination of number of dividend/divisor digits between 1 to 20.

In total, that's 20*20*100*2=80000 test values.

As expected, the ceiling for the fast short division is lifted from 8 to 16 divisor digits,
and speedups for modulus is noticed in the same region.

The graph was produced using results from pg-timeit [1]https://github.com/joelonsql/pg-timeit and R for the plotting.

[1]: https://github.com/joelonsql/pg-timeit

/Joel

Attachments:

image.pngimage/png; name=image.pngDownload
�PNG


IHDR���1�iCCPkCGColorSpaceGenericRGB8��U]hU>���+$�������5��lR�����e�m�,�l�A�����i&3���i)>A������[�'!j���-��P��(���G��	��3����k�������~��s����,[��%,�-��������:t�}�
}�-+��*�&������ �������g��PG�����8�"�e���]�A��	�b�	�;l� ���W������2�_E,(�������#�Zs���<5��)"�E�6��N#�����E�k���O��0}����*r����U��t��.i���e�i	�#]���r
�>�cU{��t��7��+���g��xu�<���D��1_�
u~R����*-�z�#�Mi*���Wh6������f}�-gi:��9�f�A,����V�>�W���B�_-��%=�^�t�0u���vW����9�%/V��B�W�'�_�t����M�������P���\>����@��y�0`D� i|[`��
�h���h�������)���Tj�����0B��#�����hU#�~yh�u�	fp#�1I/I���"��0!� �'�Sd�d�:J5��"sd����y#R�7����wA��gd�����J�7����k���n^:}nW��FV���s�t$gj-t����r���_���_�7Z�~��V�5�4�V
}�o[�G�=Nd>�-Ula���Y5V��}�x�g[����?�k���&���>��s�r�q���]�.r_r_qs�Gj�y�4k����
�i�Q��BZ�-<(d�=���dKO���	a/zv7��]���od�}���s�n����?TF�'|���3Nn��#I?"�m�z����v~K=����s�l<b|_|4>?�p����Q���r�����i����������b
�2*���(��������h��{28�oI���y�es�8�';�Z�9����h�6�g����>�x�Rx'�b�8����WO����[xn%��|�^���z}�������%x�c��8eXIfMM*�i����
E@IDATx�������bAT@i��������b����^���{/�W�?��
��{C��Q�b/ *�?o��?;;�;�����y����d��O2��3''-	��H�H�H�H�H�H�H�H�H�H��#a:&#          M��ev          �T�XN���I�H�H�H�H�H�H�H�H�H��Xf          HE���T���H�H�H�H�H�H�H�H�H�H��e�          �T�XN���I�H�H�H�H�H�H�H�H�H��Xf          HE���T���H�H�H�H�H�H�H�H�H�H��e�          �T�XN���I�H�H�H�H�H�H�H�H�H��Xf          HE���T���H�H�H�H�H�H�H�H�H�H�%�	��!��'��~�A�v��Mu���j�_��o�/��B�9R}��g��?�P]�vU��wW{��g~b��@�~���=[�?�RXu�UU�-�~5���w��j�����NP�/���k��!j��qj�-�P�������#P�M��>	T�Z�Ob����k�c]���%�	�	4!���H���b0�����k ���Cl�F9@�[��;���sN�?L?Yr�%�g��$�h��f��9�������>�Y���:K�&�������r�������[�D�f���?������@5���$Vy�K��8�U��X"	�	�@��+�&���*7'�w�}Wm�������	��5Y80l��q���W���K��
+��1�H�v	���[�����^v�ej�9��������v�i'm�|�A�n%(	�	!��� &  O������
	�@��:u�Zy���3�<S{�UX"�H���OWbm�O�{����J=�����GQ��zj�y	�@U��>az�6�l�z���'�E]�Z�l��x�	u�M7�g	�	�:�u��B��H�H�����v#U�u!�'���_*�LFh������_�I�L���sqp�5�P�,�Ld�z�$�����G�7�p�:���g�3H D����/���m��qf�y����������1��ex��7�>G(�o��F��];��{���;F%k��bm�t@����]������XW��aA$@$@$��Xf' �& �T��(Y�o��������^�XH�>g�A�K �"$k����Zl���7�|���rK������G���ZJ����SN��3bOh����M���$�����:�:��I�H�H {t��=c�@$@uM��?����i��ns�H�~�z��Z������g��j�5��i���Z��)x�	�@��XW#
A1H�H���@���i�U��/���K1�����W?���j���Zb�%�������~����;Qi�A��������cm��k��3���^xA=������?V��3�Zg�u�_���u2����_���V[M-�����%m����j��	�o�����*����7��Bnp���+����^X����v?ju�_I�b�J�+���������_M�4I��a�i^����F������~��G���r���n�^�z�9��S��
j&����1c���bM�����;����V����M�1e���k���>����S'��J+�����������w�}��]w�u��s���?��3�_|�E5�\s)���W_]!�r��/�������\�s����S�'OV-���y��w����V��>���aE�6�v�m-7}���~.����V�~���v�/�������u<�r��}��
���M�e����������{���v���|\���+[��T��)m��oJK
�,~q_�4zX��z������y�W�,��s�P����\,���.���_V?���6l�:�������x)�@n�����Zv�.�M�|
m����X�]��a<�������Zh#�)�^�������.\G��	�	�@C�0C	�b$��Z��n������*G2YH�����\�9����������K�����D�y�e;��C�Y�f{���M#J��|�F�T0�|��<��B&yY��v��������@��io��f����B�r�|�cAp�A��LGD�hN���E���w�yg�����3lZ�OD:�����3��(wmv����M?d��@y�h[�Qy"N���('����w�����.
�@�:��p����������+;���1��K/)�L���e��q�(�#�.����(rU�W?�+l��v���mQ�����o��0���98��3����] 
���E�������F���l��S>�S�vK:��;��>q���y��S>�W_}u���r�q�w������F���F]�9���#
n{�|��ST�Tq�<�����ky�hSW�B����9AnW�f����p��XT�6�q�7|}^{�2�����H�H�����1T�����o_��rD,r��
�k���X�b�c���@,m�#F�cq�2X�$�%{������[�<Qv�-�������[�t��,/�"b=�JaS_���r���x(�n�����5����M/�����~����s��G���}_r!3��
����i�F�27'���_�L>^}*S���[�bm��c��_������Ss~��"�R	�B:�\7��4i���P�,\���;��������s��
�u���e��@����y�>�i^�ND)�e_}�UP�v�m������6���n>���k�H��V�>��?�m�$�c�a����G��Gb�(=��Cs�nR�r�z�>���4��(��}����r�����������M]m����X�]��a<����Zm����^��|_{�0��^$@$@$�L�X�Pk����L�d����E0�;��o��t�w\��g�q�}9���o����	��3�+<�A1�y9���Kp������-�0`�=����r����%��g��2
/���#����M�������n�x��y^y���6��E�U���dQ��4f��\(��Jw��^@�
����E���.kew#y
S/�PP���/��9���3�{��+��Z��1��&�;|�gS~�N���e+���~�~i������+�/ �K/�4�U�}�,\��5��Y\E7�pC��n��C�8��&������.�����W?�-���4}��2���x�!&�����|<���[l���`�������n���s>�Q#�+��]�>��?�m�b�����0��������F�0�a,�}}�}�������T�9}��16��+S��s��s�=2�|=������k�g������e����+_3�G�8U��|��}_{�0���a   �f#@�r�Z�����/g��^(�x��6-^���)��*
K������U�y�����m���q��@�`m�1��*����JI��U�~Aw���F�x��/��|��Mz�����B,*��k��A9e��6�t���)������",�M9�Z�r���.�r����o��F��f
|<1iai?s�LsX��/EH�������{N��C������K��I��EXv��l����@�l�6��\r���np�6�,�e��
������6fO���������������J�bu��p����|^�a�*��|����Vl��5�&�I�����^�8w�����m:s���l���������A|�'��Nw�w�s���e�����^���}������O�Q������k������8U���������Wc1�	�	�@��b�-%\ ��B~g!�,"b����_��6������-S���Cs�A�i�H��c����`KQ,���u�`3e#����Q|�t�hD��X��4�g9*���(M��HP(����
���|Q��L�e�������*T5m�%���i������S�7lQ�&��=�~aXj�������d�"�us�8���
�t4u�{�p��O���/�X��7\%>@������K|�m7}��5��V�>�EJ�n��9�����HBX�����#G<����k;�b���#��/���-+��2�Y���������
���P�{��s-�n��l|�o��9��6�xTocQ5�e���gq�U{�#  hFs��C���V������b!����`��/�x�q�����i�v_���mw�4?��S:
��C�{X=�������d"%J�����s�=7�z_,	�X�����:�����4���=z��v7P?p@z���W���J�&��=��S����z;���\X�[,�u���:�������U�W J����k��9Vk;����E�%�J,��(�Hu�I'�4���n�7��X���p��e����(�s���#�beG����O�	JSv�������J�Pv>�iN�v����W�A����Y�r��D���?��n�8�b3�Y�S�����*�'��b������DY��,n��v�
7�|�P��*�i9i|?�d.;�\��n����/G���|�5�xT�cQ��+�F(���>�k��c]�]�O$@$@�B���f�m�)>��ca�+^X���U�cb�h6��,���8�%��J,��L�U=z��I#�W�0��o����s���4s��e8���6.I�x��h��^%.�~�����n�����7P����%nl(,����o���+�XI��{����������T+s��Z��Q+^b�J���ml�������o#��L	K9�_���(���������,�]�v
z�36-�/n_�>��[���,���>�!b^���*����O��[-��b�k���LW2��Gml��&Q���|��Q����e��ld�
q���)�Ku*7��������k��m��������f�jq,
�q%�e���gq���S���p�p�H�H����Uhe�#����K%})�F�-���N�x����*�U�~���o�Q���_������v��z2��'O6�E_jLB(�`�Pjp��C���X���	��&���u��e�?
����Vx��n���%�6m1������
���������H��(XYds��&�hK�X6J�A7�8Nd������T>�i�%��o�d/Q\}Z-��J����S��V�c�+S�k��K|X������IS�������l�L (�e�N-�7�|SH�D��}
R��\�6
���r����w\��Gn����J����{����xZkc��k���	�	�@��b��-��K�]|��w�%�rQ:�=�P�2�@����'�i�H���n�����F)�r���?_�eY�K}���Q����=\ ����i�b��.��JM�u�]W���jf7��U��+��5��D�p5i��@���e������cS�D~�T,�y)�!$Z��l�B�S:�g?-TN)���I�.��\�}�}*��Tn���X���D�~�t�h\j(�^�r�Q��|���b����
>���r���������.G�p^Y�7�x���Z}��D�o����\}���2�eq2O  �eT,W�ud�0��:�h_��";w��]d�B?
����	d�=�i����!����Zc�5�q�Zy�}�QQ���	I_e�
sJI������.���3m[o��#W��cc�������-��r���XeU*��KYD�f���]��.�Y�o��,NSu��4M�I�f�7�|R'������F+����O���;VTr,-�g�����2���97�o��z��i_����~�U�j��/�K�'�X�2�}<���(���h#��^���]Xw?�90�k��:���&  �f!@�rZ��[l��U*�a��#�T[n��V(w��!G���dq/�d8p�>�0�X�����P�[��fx�K�Z��D�&�d�.��b['�M0~x�z�
6����)��W�Xx��c��n8O���:`j��O?��I���te���c�b6l�>��oH�*��G���5Un\\-�'���X�#I�;����>KrJ��9Q��s�G~�xmB��&=~�s\n�B�Y=*3�1�>�l��������F�_kcd�������v�D��{}�^���J��   �Z$Px��Z��e�2�{����'�T�^z��t�MUX��4p���������+cv�=�h_�c��U��Fm�����d�.|��|]��l�/���Ksj��X�����m�p^�����3���S.�$������S��z�:t��6m���-"���m�/��C�v�>�T����EMT�&`�g����F��}����4�Z��	��9���R(���#��|~���BY&:V���
�R��9n^���DY=%-�P�j�i!�J9V�c�[��Q-�E������gq����;n%��{��W����H�H����hy�c0a������f?���_���4����X=#�:���^Sw�}�M
+����W/{h���E�����:'�����������+��-���Nm���.����:+29��{���2�!�������W���s��A�E��S.��s��F��K.��2���#�P��@wJ�����K/��5�}�x��'r���
��o����Fi������~�������o��5���r9>��42J�s,-TN�c[m��M��3�1N����Q�� )v/	����;���+�6n?�g�����W�M���$m=�E�_-��jq,J�'�H��^�����O���`�<I�H�H�P�\�Vr-};u�T���S��s�=7'M��2����#G�{��W������v�)'wJ��6�LG���s�q�lO�>=V)�����*������P�
�7��P��n�B�y'�p�]��W_}�>��/��B�y����v�l��Fi�r,&X(���a��.��N�5j��H��V�PN
�Z������'����bVD�^������M7�dv��|��F=|�S��7J�H���5���r��rB�|����2�����K���\r�9���{��g��_jD��z��{�	���&`
��jK�u��3P��D��f�F�Sj\=�E�s-�G�8��O�=���>�k��c]�|y>	�	�	�+*�+�r+���-n0�L�b��
(���97�J��6�������W]u��,B�~���@�����w��6l��B��u�����k���u���+�h|��G��'���/�����9GuT^�<��U$� ����/��F��fX6���[�����n`�{��7���(�]�a���m���?����Z�k�x���n��)��g��������U`_y�����������?V;���m��]�jw$��+��E�E�����>��(}#-��h���M_������Xj�+��!��9d�����7>�0���r���]���O�>���_~���6��f������[�[&.�o��@I�/���mZH����y,B]k}<���(m������>�k��c�/���H�H����(�2&���o� �����Yf�@,pq_�n V���G��v}\�������lA	���5e����1O;���s��m��l �Q�X��Zo��] ����z�d��W�6������Dy�ur V���������r����@�tl:Qd��A�(�y��;���t��B�����-u��X'���{���������M��� ��@��l�G��2C���^{�����i����E���[o��h �������r��&�lb� �v�m���@���C=��<h���M#/��L��j�w�i�������7���{/|8���oJa�F���[��������Sf�t�*��#�����DD���="���|�
q�cY������H�n���wT��y����g������[����X���K�q����������1c�|���1�������u���'�s���BV�W^y������?J��xJs�����e_mZ�s���>�"��F�F��\��6U���?|�����k��c��@$@$@�HS*@J:�E4n[���y�/�PB
&L��
�4���o�?_N�|P�B�����b�i��I+��Td���2����E��fg��������qAK�i�7���K.�+������#�[��m<T#}T@_��3�<��G�@`�Jb�X>��S"��o[t��+(<8����L��W���"��l�y)�in��R�9Y�,�E�}�t�b>�iQP'p�R,��i�I������[��>��M#��>��?�m�$����4iI�N�`�����w�uW�����t�*��������e�I�j�4={���AI.���N��(��Y�]���4\��}���_c�J#_#�G�8U���?|�����k��c��@$@$@�F��0�M�n~�a%���u��M��K�4KR�)�&`;�/�+����_{���h#l�����W_�����T�m�H�����$��]Y�KZ��g�{����:��aj'�\|��y:T���6>���{��Q�	�����g��}�e2�"u��Vb��0
�]���A��m��S��v����Sb����+r%�u�0����lc1�[���G�I(
3���~�o����W\q����=�q���B;�/'*��|����yE���y���}#-��h��}�������K}�2y���<���W�\�w�}z���r�����e�	xI��
���Zk-��c�$�E���(�����j��bL^�c*W��Q-�E;D�}��}_{��2���I�H�H�f	��&�f�k@�� ���O����Bp�VPb�Z���Xu�t,\��A��M�4I���[��#�@��������<|�_�b����Z����1�4�e���k��CY�����:�-~��\��n���������d���P��O���O����~�[�z�iy��F���+}-�'���X����?e��p�����S}��������J�7���w�m8�~���M
��
��TOm��0�n�<��X�*��^��������Y	�	�	�
*�k�%*,���yK/���E��2W��
1;u�d	���,�H�H�H��J���W�y����s�9'6(x]tQ%�/,���0j�Ml<@$@U"���J�Y,	�	�@��+�&mz����2c����Sy�?q,	X)���	��l��H�H�H��U�,l�%�������Z����&��u���H�8��'�	�	�@e	P�\Y�5S�L,��"Z��3g�A���v����1c������@$@$@$P_N=�T-�_|��@�I�W�Cp����{�%c<	�	�$�u5�,�H�H�A	�F�6l�j]t�E���N�I�����"^$a���������[�s�=��bQ,Z�@$@$@�H�@q�+�1�zv�����O�>}���?�]a�7~��-sD���-��R�=����}FN"��	$"��(�Lq��+3%  �<T,�!i���w�]�1"Q�����[o���U��H�H��>�����0�<��E}�W�|���K�������5�\�=�P+���,���{+��` (������{&��r	�|  HF��0�qj�Tw�q����{�k�[���ZK
6L�5�J�XJ<@$@$P0��_-���X����/���}��j��6k|<�R�k��j���6�$@��=!?�d8�%��T$@$@$P.Z,�K����2e���=��F�.]T�=T������
	�	�	������/���6�l3��gO
�'O���\sM��j�	�	�=�uu���	�	�@��b�����	�	�	�	�	�	�	�	�	�@��+�Zk�C$@$@$@$@$@$@$@$@$@5N���o �G$@$@$@$@$@$@$@$@$@�F���Zk�C$@$@$@$@$@$@$@$@$@5N�e��G�R������?�����{���Oq6��;�I�&���YWc�%�P����U���O�?����u��:t�`�U{c���j���V�UW]Uq�s���7��u�|>%�f����-����E�y��v�t�M������G4Frp���~��Z`��2�,�Z�n]R�����?Wh����_�Y���#��Y_�;)�J��T.�#   ������A�����4�����k�V�FR�{�����w�������cC��9V��3fX������E9rd�y0��	d���K�H �����[
�����r����{�(C3�4��dR`�L_z��`��6
��o>��h��,����	'����D9~��7��G�r>/�
6� 3fL�||'*v����>dKZ^-��	�	�	�@}�+��jw$�'�����x��U����Il�J$@
K����'�O<1�6�e&�����c�=��k���y���/��p�����_�K.�D-�������9�y��W��K.����J��o��F^c��U}��Q��w_�1����~�/-cH�H�H���]a4KK��$���N��V^ye���V�Z5xmY= �}�8.Cy����o�������S2��V{���S}��U���?�K�q����C�*�]������z����������g���~�I����C�U���?���{�=5z�h%��
�l�3l�0���{������~�F"  h^T,7o���MD��#�P�l����k���5�B$@$@�!P��Ro��������M���Zf����������zh������:��c���o�`�
����/� �{�����8������~���Zk-m�����4��r�:�����Q���N��v���m��4��(��}�V��Z�7�90?   ��"@�r}��%�����K���H�H�|h�{�_|�>�`�X�/6���UW]e������E�F��V[m5��V��=��vEe����k��'���X�.3\�2`�^YD+��o�v�q��7k����������.��lY6	�	�	�@�����iK��H�H�H�H !���������/��T���9��3a.���/��������j��6�_Y����x�
��
WI}���)���g�u������@$@$@$@$Ph��q;����z� ���K�bK���Y�����[Nu��1Q�u�]W���g����/��W_�m��QH��:�|�7����78a���������*���e�YF�1G�w���zK}��w:;W��>�L������j�����/���������kVI������_��C=`}��wo�������S:�����h;�����3(+�+YI=6/��_���y�%���$K-�����k����d�m����?�������>�H�o�^[O�������_��4�C��R+��[Q�_}��e�p7e��*0���T�N��J+����S�P�����b�VY������~�7�%-����9��o����|_�����p�	��S�y�mM7y�d��B��e��wW�e���U���-���X���������i���'�q��c<re/g�G>���.�}u����}��?���^zi����z����~e'
�|�����;.��>�_�����L�}{��!����<�_�&��I���h��C.\���o����|��j+���|0���p��I���*�#OJY�5������ ������<���������{w}
�=�`���G�WN��j���?   0�E�!C�	�.��g�[�(]Q`����vZlZy�d��N��"������2��/�����3r��o����<�����w��hD�����9��c���mW����*�EH���_�~�Y�%'�rvD���0�<�F|��/*�u�iQ(�� 2OQ��]vYT66�w~�����;�l���=&/�9��;����������-�p��X���1�1cF�q���fQt��o�9�-�l��
�+Y����{�,0�����SS�o����Q0g�y��72��=�RN�>�-2t�����w��h��c��>e]k0�����ey�T�@>�D��G �:���
�D�n]}�G�N>��j�w����6>�;��(�#��VXa���G5������q������n��_
���n�o����(�mr�0e�}���6����LP���"���W���@�Z$:e��w��p?5A>��x<o�������}��/�06]�>�����e�9�����!��!B��^{�4����U^)�&�1���_   L7c���,c"��,��������)^:����)>m2��l�=��t?�����6����m�
���I^>be�hN<5��rK8���&��X�����HV�Ef^$�����+J|�����72�c �y��u��00��uy V�v���%T Oyy!�w~�*�}���,�"�[��a���
02��[	��X&G*���G#�X����M�J�um��v[N}M9ba����~�L�������������X�G�����E]T�z���(��c�m\���O�i��;��nS���������>�:X���bQ���/�qt��9����o��sO�nT��#J����������m7_�/I���h��2k%/y��>����y�����s�3�!��%b�8>�%	���=���IN�M������n��?�x��N���h�xa�����c��s�H�H�H��X��@ik�Pf�)q������N���t�H��0<�����W(;���5,���Z� ��Gm��������/�g�}v�����tP����O�>6
�K�ppe3
(�o���/O���r���]z����R�����1,b�A����|`A�����/'�q��W�[�|�U,M����p[^y���p�����U,�jkT���Kx��|���?jE;�@����W��U,C�'�K(M>P#����}��kYd�������xQ7/6?��K
���X�C����-��"����g���o�������|����p�	�h7���5�^X�p�
�Z��X���R:��#	����i��y��9}`������n��g�M}�G>��j�w������ww-�13�M3�}����`!o�'f��
�|��S����v3u/��%-�pz���4L|���������m?�Gq�a�>|�=V�P�� �-a�^�s���y���o#��_~���c�{��7��$\�x�0`����~�*����U�1����$@$@$@$T,W��
����?�%������~8/-,D����7!�b&>�5�9����e�������	_Q=H����,>dmf#,���o�#�I��o�8�<|/����PI�P���0=�P8��mZ($�!\����LL���5p-�L���s�YZW>�������,��?�z�����I�V�l�����C�_���_L�5�`�*��A�p�����`����i�E��6����k�L
�tg��>�-d��r�?�m��=��_����\6}��^r�%��(�VmZ�[��g=!C����G���j��0�r�:8���p�b�������z��qc���� ���b����r���}~���&��b�����������m�Y[���Y���a�I
L���Qj�y���������0��
#F���L�*�M~I�M%�#I�H�H�H���
���5���o�ts|�M7���|�t��4ia�������z��5��n���Y����S��s��uo�c7������qV��l� -%@Y������1�������EYf9�$t]�DY-���U$�Q,�nk�/���a9r�H�%�7���U�F�����L�F6��
�{�0`��}^(W���4���y��-�w�Z9������n=�r%n�As}�C!�����p�SJ�]O�������������].��u��w����%�l�
��
tP��&���E�b����sG1�[�qup�����8&i���X�b�H[�B�a��C�J>����rB�&	p�b�X��|_���7,��l���c����H��b��cL��� 	�	�	�@S�Cn2&�����D1l���O<a6���S����2%������G�M�������V�k�p���q����0n�ac��	J�:N\y��?<�xxi����v���o�T�:m�W^ye��
Q���'���S%/hJCJ,��X/<u���9.��9���+z�YNs�1�p!H�;?[p�
�m-/WJ��u�2%S����@��T@_�'�8�@��,Z|���N:��A��
��T���B��e�s��n�,�C|V��3�>;u�d�@^���k#�������J��v?�F��������0�j��r�:������6<�O�0.�����'�|R�W��m|��j<w$��X�r�_��_���/�����R��L�[!��|(Uw�}���?9��R��4I����qe��f�����8G'�E����(�\�{����8X�1�����H�H�H�1P�\�v�)�J|&���zG��bN�F���];����W\Q��EX�k�b��dQ��|�����7�x�o����Ub�l��!��v_|�*q-`��6V_}u{�=�F��V�����PNyFN�d_��(�?����+i5d���4b�����l��f�n���n��bqf��6|�UF\��V>���+�eh\�:^��
�y����x�uT,l���6����o�K�(�����U�E��\��6�����g�/�[�Xb	���E�
�n:w;�z��r����[olW�����!����mF&qc�?���/���7�|Ez�x��%|��/���V>Y���K��+Y�@��/��#����yY���	2+�l�u����n�����Y'��MY�����$���|��2Tr�����H�H�H����/q�WZX��q(��������)������&�����>f,>��!���y��7�@d�~�1s�XFc�X]�c��A\D(Xw���{~��$yA�g,V��G��<����$������N3qeHR�*jO���_�,��d�0�n��������V>�Z|�"e�>���x	�j��sJ�w_����X^��Q��(�����I��b����:�g�E�I�Z����m�lWq���+�O�}q������(3I���G���0�j��$\��:����#�a��)X�����X���	'���v������h�_W9�s��J?w��/.}��/q��K|��E)����-
�����"��GMHzow�z�5�F�fq�F�����'�Ci�'��e���e=�7	�	�	�@��b�Bm��v�)Y�E���z�8����:��rS�,[�Y��0�ec�����`�xc����JQ3�1.}8S���B�Ri>y'�����*�������R�
,ddq��CyqIae�7�|S�b9M~y������	a�M|�����:�.('�� �xI6S{?�����I�����"�r�?�m�e{�}��p��<���gYO���O��E3����z'�
������u����#O��x����,�k�M!������X�{��.�(��������������W��K�%���Y�ik	�-{�����/����Q�"-�M��b��;���_7]���Y\�q��e%���q8k�r%��86�'  h.T,W��1M�s�����g�U�B�4B���Q,�b>�1������Ciie��S3K�]+aXW�Of�P��7m^����L��{8�=0�V��/�������s9��n(uj���w~&_�m
W&&��'	�o�$�KM���ZG��R���(\��E��3�W�����x�m�e{d�,.�)|,�z�����?|_������D�v�����{N�b[�/,f���5x�`%|i�PX3�
�����~�����.��=�X=�q=z��kV��B��~����
%���tI�������{��u�&�&Kn��vo���x����S��<�H�H�H�1P�\�v���o���	�F9@IDAT�x��"�(���h����Zk������S���+'�,�*��J��4�W�����iyYd��V6Je�py��z�1�:t�)6�H`!�8,���.\+o(W�������������v-w>���b���.�D'�������O?�4Q.�?�_��"E�2I�(�~�B�������#D����Y�����O�F��j�N+K8���������>���`�B�x.0��^~�eu��'�t����0�f��z�H��?P(���	x.��r�{�YW��C)>`���>/`��RB���+�N��uL*��cd�z�1���H�H�H��	^U���x�=���wp���k��(c�l���	P�=���V�U�
�9��_W�0n��r������<,��|�Iu���*��R��}�\e���$/nX���s���2�n�b��s���nk�R�}Q��<�L\_�xa7!�b�M����c����e�-W>�m[�Q.3��u=��!N^7�;~�������o������~�!��x@�rs�]v���h.���&��������2*��"	T�ks��p���3�$R*#�|0��0si��	E��k8�^{m�����=�P�n;%q���E�_�Bygq,�1&Y�'	�	�	�@}�b������F�2������b����Ri�+����l�w�+[,�y��j�5��/�g�uV���7�"� Xml�����c7�B\0nI��#������a�^(���PY�c��z����E�E��Qc�oO�p�}D��d�(��v���R�i�����,�m�b�n�zh�r�����Y�����O�������_���p-�z\��n��Zx���Y�7����zz���C��g=^�y�9��+���&;�����������zk��y|���&f�����,�<���{TlAr�W�^�0����w���q�u��B��N��7�1��,,O$  hT,W�)�P��f��'N����5!�X��C��	,ma����2�X���,~1
.00���#�(X�P&�{���9�<1���eH�N�
�4u�Tu�����1J����w~�a����F�q�mw��w��;��������_Tqq���W��n.�����u�:���c��9�����v����{w�-��
T�|P����l���Fz�����+������(���������������cQ6��$�o�B�]�J�X:'�X��;���Qr7r\1&Y���b��y��g�@�?���9��_?��p�H�	{���*uM
��(#S�/�B[!��5KA!�O�^�y#�\_�� ]5�#I�H�H����n�m����h���rxaXl`?XAL�6MoW�

��������L@�}��'[k-�������>�(��^@�2R�?�&@9?e�����x90�����3���~�u�`�C{����v��-�����4����������F��/�x)���;����~���]I^��f6N�R��7���/f�]v�������_o����?�Xa�����k���n�L�������m��=��e��D=K?|_���I�������,��O9.@Ie�X@7��w^T|5�;���Q27r\1&�/��~����?���1���J
�^q�����f|l�q����h�G�)^j�}�*&���3l�0�,l���saH��Q���U�o�~�L}�1W_}�:��S���7�\��<�H�H�H�	��C	�el ��t-�'����6���w
�i���;���\sMl:s�s��6����Mt���{�m�@��W_=��@�:9k�@9i.����<��V�6m��<�#/�$b����X{b-���@��{��7?�����i��$+q�^��9��u0�!��^xa�����?�]|��<d!�@�9���������+����+/��(zs��_mm�_��L�����(|yd�>��A^�mZy)3Y��u��X��"��`�,�������A6�C�e�l�V 8��3�BFq���G���`���������0��%��G]���W{���r�-g�D�
���X��t�+?��Sl�b|���u�1������].>�:X���2
^�G��0����^������@f��B)�<Y ������sG�{K�q9m��y�=����������q������w��9^��#������{s�=w�?q������cY_��+3$�������
�:�C�'�tR^�D��f����N;-�hO������/8�n����,��/>���V��b�����j������'O^F�	�	�	��"���d��}P��}��)��o���NV��32-"�x1��X*�������N8!R���SlE	%j��������#/Z���������^���M���x�V�d�����\����6U��@,�
2��;)b�g���X����&bh���Pp��i�����2���;im��g�E~n_��l�����#M=��X�U�p���|^����i�8&�����?��c�xo�}����������sG1E�O2.�m7W�V���$L|����a���>�n�)e�X����������U�����c���$�eC)?������Z+g��#a��b�%�7>�*����$@$@$@�
C�n+�i�b��D!)���'{�a�_%�X�(��UX�n�u��]�L�Bu��/����-.9�T�H�i�u����a�L��|��m:���K���E
�OZ^��A���1������J���m���T������D�����+��@�|T���i����i��{���l���A7��0}Suq������;N��"�_��e��U��%��������-�z�?|_�i�5SE�z�������c�[��/�(�����4|����I���u���I�d5^�q+u����L�X^����7�8�r��Wp
w���z{��}�2u���c�=����:p��u
��e�^g��=z��nF����!I�����.LO$@$@$�8Z@��8�aM�&��'M���z�-�{�g���aY\Bd]tY�CA�X�
�� 7�iD�|�>C�!V���C������z��W�/l�/^���+/�q�m
?��3�;P`a��N+R�����?|<(V�.��/�P���?��Cb������mk�=
�(�`9��z��y�'E�l���_|������B)�T2;))��K�f\����(pR&��%���4�o����~����'�"��e2��e�N�������N���)D�I�M3�1i��iI�H�H���b�G���9�V�w~����H������k3JL$�8���k����^zi%kx�bP���e
�S�N
�3�	�	�	�@#��D���$@$@$@$@$@$��5"����1��$5��;:)��&&��6B����    �z'@������H�H�H�H�H�b`�l����9S
4(�����^�3��~���67H�H�H�H��	�b��[���	�	�	�	�	T���G�N:�$]&����O�����R������[�s�=V.,����;�}n�	�	�	�@��b��[���	�	�	�	�	T����������#�"����W��}��U��rK�a��	�	�	�@]�+��l6
]--Z�P��|��K.�C$P�8~�~QB ��&p�w�{��W����]k����a���Q�T��mc��	�	�	�	�#�2U+�G�)3	�	�	�	�	�	��)S��O?�T����K�.�G��{��� e    �LP��	VfJ$@$@$@$@$@$@$@$@$@�K��0�mY3         ����`e�$@$@$@$@$@$@$@$@$@$���Xn��e�H�H�H�H�H�H�H�H�H�H T,g����	�	�	�	�	�	�	�	�	�@��b�q��5#         �LP��	VfJ$@$@$@$@$@$@$@$@$@�K����m[��H�H�H�H�H�H�H�H�H�2!@�r&X�)	�	�	�	�	�	�	�	�	�	4.*��mY3         ����`e�$@$@$@$@$@$@$@$@$@$���Xn��e�H�H�H�H�H�H�H�H�H�H T,g����	�	�	�	�	�	�	�	�	�@�h��U���M�:U��1�6��$@$@$@^	,��b�e���S�����<y�WY�	�	�	�@mh���Zh��jCJA$@hH�0�����CUO?�t�s   hDO>�����[��=��sj���O}O   �}����:���k_PJH$@eHobSf��x:^8��{�f�:�L$@$@
I��?T#F�(�n�r�j��}��0   �� 0x����R�	�@P�\��[�V+��RJb$@$@$@� ���z)f���V�.�����		�	�	�@�	�5�\���	�@�p��
�f1$@$@$@$@$@$@$@$@$@$�(�Xn��d=H�H�H�H�H�H�H�H�H�H�B�X�hC$@$@$@$@$@$@$@$@$@�B���FiI��H�H�H�H�H�H�H�H�H�*D���
�f1$@$@$@$@$@$@$@$@$@$�(�Xn��d=H�H�H�H�H�H�H�H�H�H�B�X�hC$@$@$@$@$@$@$@$@$@�B���FiI��H�H�H�H�H�H�H�H�H�*D���
�f1$@$@$@$@$@$@$@$@$@$�(�Xn��d=H�H�H�H�H�H�H�H�H�H�B�X�hC$@$@$@$@$@$@$@$@$@�B�e�T��  C��[oU/��������c�=Lt��
7���x�
��&���w��������+��b��ml����o�������{�=5�����/�X�5�\�i���:5a����s�9��g�yT�����k��z����@$@$@i\{��j���j�}������SO��#G�u�]W���?MvM���c�U����:����B-T6�/��R-�����������V|���<y�����n7<{$y�@]x����/�Pg�u�>?��������7�|�Yd���0`������\���kWr><�H�H�H�8*��3b
 �:#���_�I�&���Z���S�L�iWZi���&���;��}�Q{�������u���{Nm��F�����(��:� ��z�J�c$@$@$�C�����������Cy�{O�=l7�	|�����_~Q��G|�G�H������_�=:��w�}W�}������S-Z��J�O>�D���K���S�]v����w��O?���)W^'[��������������*m��o�)�e   �����e�$@uNV����{�Z�Vz��'�Ry�
6Pc��U>�`A��)�O�>j�w4���?��/�x�5j��u�y��������K�t�   ���\rI�������iOm����4k�,5�|��U�3f�#F��-�_�~��'u�	'h%)fU���O[�~������X��:��#be������a�b�����\�����Z����	�	�	(��C*$@$@���.�z��i�K�x��G�ip�z��7����>�L-��b�k��md�����v�q�9�h��A�������{��� 	�	�@�Xe�U�������<���k���:�����2������3�g��]�z���.1���;(���c��Zf�O$@$@$�\�Xn��fmI�*L�d�7�K�.j�
7��]a�\�����s�=�:�����{��>��#u�=���v���i<N$@$�d�k	 ���
�M�6��O���c���������[5s�L�����
��w����iC�e�=�������n���}h5u�X�`��q
~�����R����
ekcS��/�X`��+�\���]c�����|���z�c(����>�~���V������^[~���u���G��eX3#O���
�YJ��p(���4�����'>F�j�*6[��� ������5.+p��fA?����a�`����~�p�/~�7��������jfnn�	�	�	�N������L (J�X+?���	?�p�k#,�Wj�����n�[z���J����	�	4 (|�������])�*��p_���p��c��Q�_���,~(��<�H���W_]�b��2�����K�k��K/��������7���>�hw�[����w�Y�r�����o���!o0�">~�
��	PB����������{,���
>>��\a������}(zw�a�u�/�����ZK�r�b��6��|�I'�&/(���>��#�<��P$8�����v[�N����;�An����!�bOE^x������t���_��kV�v�i
>�M@�{���4@�K$@$@e�b�L�<�H���J��g���7�|s�����k�&X�<��3j�-��;=Q��������a   �2n�^~�e�������y5t����8b�p��PP��4l
�_(�_|q��2��eS0��2����T����AX��?^����Yg���PZ�����2����j���.I���������-�4@FXVCq�{?���z�v]�YL:t�Jo(���R��%4�
UX�CI��kW���f�m�%qXXN_|��Z�������E������rt��Q���������r]|����r��a���V+�������9'NTp���S'������y�a��u(���p���3�Dcv����`���E	��������
��H��*:w�����~�m-�3�d3�	�	�	�G������l �&��SO��B"�i�qi^}�U�{�q��������KK,�����}����SX��\��Y4�����e�c�WF�	�	�%(P_x���lg�l���Z	E\��{|�B��dq.��p.5�R�`�T���P�P�BE%,`a�lf��T����T�&��_(����j��lp�Bn1� �%8�H�x&�b����`����I�H�gX�"�F���KZ{����- �6��
v0���D���J��y�*|�EQC�Qg�y�^$��P�#�J
t`]|�W�g�'�|R�>��h(���e���������������������������[�GY�yBA�����b��
I�H�H�tT,���g�	�8X#����'��0.X�D��"�_��X��T����E�,5�&���N����.5O�G$@$P�^|�E]�=���*�M���c5z�h����G�n��Z����������{N+9au\NH[����G6JeS>�PJB9	�r8@!���(��r8��>��������1,f�1�X0���{�����l����K��/�\M�0A+��5�0������������n��J]�G���X\��9r��z���&�+���7���g���>���a��b���I��W/�X�3	�	�	�@��X.�!s �Qx�5�J�D��F����&�:f�������;����������)�����}9�ec�����[�I�H���7C���p��
�WX����������d��\j`F���k����V[M���&��V����������|)G��P,���X0i��.6�l3{
�;����/g����6�F�����9I���)�M�~V"��:����xh���b���~�
P"C��E�L��j#��m���7�gXEG�_�c�Y	�o   ��	P�\>C�@$P�`�����]�����x9[g�u��D��Bp�qO4�`z1�����M�d��@c�l�0��LC$@$�X`��{�oP�E��gT�Ai�&���jy�}��I}����X��������i���9l���a���,��3�{�i#��]��I��
+(XoC��?�	�P�c�F<$	��s�z��7��B1�����q�'rv<��r���!�&��G����k(���B��E����$@$@$@��X���= (�^��K7^��,r`��p��U��)�i�5B�^�����$@$@�'`��={�v���k�2�+\U��e�h��`|��������>�@�/���|���	�,���kcg"�Q��S�(k���em��-��P�B��_��B{CYX��b�9����#��3�9iX�c�7��]t�^XyBI��hE8�
n+���]�6�2���+�v�R(-��	�	�	�F �Sei��, h:/���������m5�,^�����X����zHg��0�L��	�	46(|a��E����QP��N�_���e����Bqh���������K.�D[����q���5����"���G�u�������~�l����b�=FZ��
�$�Q^��2��������Ok�i,.vaKf�0�;1����u�w�����M>q�D-\rn�qn�	�	�	dG �<��d`�$@$�P�({Y���}`u<~���� '���6�l��|�@$@$����o���y��^��M`�����>���/L�#�����������-m�7�X���B�@��3�a%�r�-������%r8@AP&C���RK��{,���E���u�R��odW��y��P�"�tX��x�bF�9�>< D����C�j+mXm3�	�	�	T������H��|��(��n�����Z.�:/�X�����+�������d����q  ��#%-�R���N��dM�/�pP�	�{��.���y���������2�G��42����%.��!�8����5�����w/��B5m�4sH+�������^�"�6���[o�U��0YBy�u�)(��1�(������
~��1b�>n#��@[�����:�������u��3f�V�/���9�:���%  ��]ad����	�9�Q�F���G��f�q���2^����Z������Q(��)�p���&�-{�48����v�mg���H�H���(|��p�
��#�Pp���^}�U���o^��k\p���W/�����$�&M��(7�h#-���_�-cq�����������[��~�]%mR��uB��m������w�y:n���R�:�0���������
�$K,��:���*&6�4z���?��2>�O�4I-��2��O�r�#�a�"���W�����01a�����K.������6�_"`�������]w]�`���/���������������C�`�Vn�	�	�	dN`��K`$@$P���-�g,r���L�VI8����9�en����)L���m���v�e��s�C$@$@ ���E ��-�������Yg���q}�{{Y�$e`�9����SO=�����R�t(>���^�,�M�\����O?�T��R����.,���q��7��KP����(e�	�Cy�p~���+X/C�����+�Q6��
�3�<S+���}m�?�W^y����v2��E������q��!5`�=[�U�V�����u�����A��5�\���	�	�	�@�����r�5_Ix��EH����G�5&  �� ��ohe��O>��u���R�����.�L-������	$���B��
a���ug#X�~��WZ		�b#X���������Nxe�;|d���q	���j���Gpa�Z�a��br��9�Z��(��(��b���\�ec�FXoG-����!�,	`�f�|��Y��I�H�&�FM4�     ���,��?���K]�`h�Ej\���]���h<�v����
��
e��".]8A:u����P&S�lqp�H�H��J��0�����	�	�	�	�	�	�	�	�	�@���r��%&    ��!�E���Z,������>��	��z�v��&?����`    ��Xf/     (�@�������`!�j�h���4����4��SZ,8k����c]O�)+	�	�	�*����(#	�	�	�	�	�(�W\Q���,��8p`�DLA$@$@$���c�)���&         ��	P�\:;�I$@$@$@$@$@$@$@$@$@MI����lvV�H�H�H�H�H�H�H�H�H�J'@�r��x&	�	�	�	�	�	�	�	�	�	4%*����Yi         (������$@$@$@$@$@$@$@$@$@$��Z6e�+\����^=��.���	�	�	dE��������O?���i�%/fB$@$@$P}���[���$@$P!T,gz���R��OWw�}w�%1{   �J�{��U�-J*r�9�P8���/�|�D$@$@$P�p��7��s����`  �4�XNC����g��U��<�H�H�H�Q	@!���Fm]��H�H��	L�4I����u��O�>��+��+�),	�@�	P�\�6Xl����\���WD�2{����X���2%���j�����y��G�j��2W��1����/��y��	�Z�4�6~�����������T������3�����������&�O?��f��������	��[�������� m����v�)���/�Pg��eKu����8������sg�$@�L���
�n����N;�T���W^��N����A��iM?�����uk���V~�Jf��+��*V�{��X3(���:���c����X�|��U��=+���Q��i��by���F�/�CF���s���_��L�:���A�2e6k��"�,R�U.�m���3�by��6��q�9=������I����\9��H�H�H�H�H�H�H�H�H�H�?*��3e�$@$@$@$@$@$@$@$@$@$���Xn��e�H�H�H�H�H�H�H�H�H�H�?*��3e�$@$@$@$@$@$@$@$@$@$���Xn��e�H�H�H�H�H�H�H�H�H�H�?*��3e�$@$@$@$@$@$@$@$@$@$���Xn��e�H�H�H�H�H�H�H�H�H�H�?����d������T��^���S��N�:MWJ���g�I�&����������,�����o���s��iKI0s�L����6m�=}��Y
���g5�|�=	&O���t��(m)����k��s�RN-z���?T�/�x�m�����-�����L��Yd���UJs/��l����+��k�)�;���0�J\�����Zn��
R����������2+1���7�|�~���L��t�>}��x��E��m�D����*����G�cc�m��9m�gv�q��F�A�c�i�,��p�{����u�����O��6.�He��u/��j�m�-^Q�  �&"������������3����P��?�����������)��B-��M�V���N����?��,q���Kf�������~5c��&m�d��������������.�)�������a��^�)�X���^C�c��.�~���z��rC)��s2������J��W^���W�h��q��=�X�DGa$@uE��0���(,	�	�	�	�	�	�	�	�	�	T���oJ@$@$@$@$@$@$@$@$@$@uE����j.
K$@$@$@$@$@$@$@$@$@�'�p>����{����G/r�E8:v���U�~�T�"������#�k���}�-��Rj�UVQ[l�Ef�E
�H         �
�X3f����������X����_W����5j�8p��d�Mr��hv�a��/���X4��G�/���:��3��s��swH�H�H�H�H�H�H�H�H�H��	4�+�����*���w_��c��{��G����^Z�<h� �@6�~�������ZK�=Z=��j��
+��;V]q�&)I�H�H�H�H�H�H�H�H�H��@�(�|�A�<�t�M�~�����g���=��U����o������w�yG[3�j�J�w�y�M�6�P��]�e�]���y����?�S�K$@$@$@$@$@$@$@$@$@MO�a��������W��F�E2��~h��u��n���w^�m��%��k��f����\f          ���Q,�e�]w���^{����6m��o���=���o�m�t����ba������H�H�H�H�H�H�H�H�H�H�a����.]�D����i���_~y�~�\e�=������c�������
?���������3�W4.�����*O�m\y���n�������'�6�<�p����{��6
F(��~����w'P��e�������g�L�!���I@B$�-��#E\��"E���)��vTp	���$�c	�HB��L2��=?���C�Lw���Vu�z�sz����oy��.���[�Z�������q��V����U�^_����P�[	������������LOO�<f�b,� @`T�X^(`o~������Z���^x��Ew��Y�=_by������r�V<�����u%���U�9���M�R�Os��v��{��b�_o���@�v�]�hF��Q�1��q�N,wV�w�������X���������~v�Y�nR��1���	��6�����@v�#a�����~d����% ����
c>���,��l������������2�(����s��k�V���4�s%O @� @� @����b�-oyK�����*��{��{%��K$�W�ZU�����������js���?��yo����|���06l�0���|rll���ikb<�>7)�}����A�U(b<z���/�mu�^�f��zU�9>�n�V���Eu��m	��jk�.����.��*�1���	�a>��q�Y8�1�B�cv(�r�C��`	�!���r���W��U���p�7c�\rIy�c{D�6n�X�����w���Vo���gQw��g>����u����S���60��5,�}������y�Bcl��e�;�:n�w;DYl��C�Vm��7�tm������s����o����-�2�VB��g� ��|��o!;�0nu���~����&	4�V������*��H~��0gR9���(u�z0����8��G=�Y @� @� @`��X�D����������<�(oz������y#|���W��p�
s.S?��g���'	 @� @� 0��I,���^���������y��UR���NZ0�\pA���W^y�r��~��G���=��#^� @� @�FU�1��|���k��no�������������SO-�]w]����g��w��]e��-��SN)��w���< @� @� @��(4��`���[]�������������3�8���mo�^�����/�����K/-�E{�7o������Dy�K^����jz� @� @��QhDb��o��|SSS������^{�cS^����H,�c�~b������/.��s���= @� @� @���4"�|�Yg������X>��-�]vYu��[n�����m���,[��;�tmcE @� @�.�����������[�G!@� @� @���$���i�+����\�$�nK}s���.�|������eog��������go����}��fv����:�g������������}���}cv��>M�?;��7!����d�/�������o=BK @`�	H,/���Z�*�7qk������}2���&��}���y��%;������x�1��k��;1���g�#D�z��y������]f�"��w�a����C�?�%��<~�J����5+rK���C�s�	������ ���%����p�\�2��ybb�d_U����$�1�LLNN�~8�$Q;�T��f~�1��sg��j���3?�j�'Kw��go�b�zn-��bE"nY�����]f��D|�����U����+R��q���C��Ff�.��d&�#�������y�}1����^�:�H�:�N7t!�a @� @�V@by��Z'@� @� @���	H,]�t� @� @���X���	 @� @� 0t�C2&@� @� @��`$���u @� @�������L�	 @� @� 0X����k� @� @�C' �<t!�a @� @�V@by��Z'@� @� @���	H,]�t� @� @���X���	 @� @� 0t�C2&@� @� @��`$���u @� @�������L�	 @� @� 0X����k� @� @�C' �<t!�a @� @�V@by��Z'@� @� @���	H,]�t� @� @���X���	 @� @� 0t�C2&@� @� @��`$���u @� @��������^�vm9x�`��o�^V�^�V����S���o_���(ccc)c���������,f���>�&''S�����'5�1����]�N!��q'������{Sc|�����#���//���|��m�c.���go��1���:���vJ7��;��������=��S��[��^l����mo�v$�\����uZ,��]F��V�j�k���Xg���m���B�����~��6b���v��:�?���k��9��&�1�c�9&~���q�v�g�8���^%��QG��1����9K,��G�U7�9`l�Y�q����q}�����Y'�ow���z�5������2��2h��1�q��Bf�f��g�x����'<�%NH2K��
���[�������-3���Y�a�$SV��v���U}U�/����#������7���h��M���n������;�������7��E�1�D�(s���w��-Y�/��s��cS�D2*�����q��7b�s���9g����C�d�8�E��jV9��cS������s���f�Gk���k��Yv����A3�	 0H��K�9"m @� @� @�@���r*��	 @� @� �<������ @� @� �* ����r @� @�4O@b�y15" @� @��
H,���� @� @���Xn^L�� @� @�����*'@� @� @�@�$��S#"@� @� @�@���r*��	 @� @� �<������ @� @� �* ����r @� @�4O@b�y15" @� @��
H,���� @�P!��@IDAT @���Xn^L�� @� @�����*'@� @� @�@�$��S#"@� @� @�@���r*��	 @� @� �<������ @� @� �* ����r @� @�4O@b�y15" @� @��
�����r���2==]���O�@�@�7e�b0X�&�n
>���8�����A�s���2X��`���zv��������������?���V�����	������r����T�7�w�}w��6l��r��,�m��r�1�,�����woj��v�*+W�,���\h'	��}���s1/�V�^��*\7;Q�q��`����;����/��o������;u;��c����/�QV�y:����={Rc��}uv�o�����������b��I���cs�s�;���}��YS��vy��'�����6����������.W�Z����4��N>��������q�d�{�'������N2��1O3�q����:*mE���Y����93�����q����i1��|�6mJ�?bc����3�M���b�]�6�h����1�V��\�����i�U1��@������|���������+��2������+������i�G���+������9�H<d� �e��8	��Tv���C�1��vo�2K��g�8�(�vo�2��L���S�	�V��u��U�w������j��"�{�UW��K��c���zgV����g�Y���H�d���?s��evb�e%:��H
�OV�dWf���z�=�du�LLL���(��_�>���;q|����}S��#>8�?��C$�3��>gnQl��`�,���*qL���{���>�hu���c[���i�Q1����rr ����O�����!p3�`E���~tz��q?�n#��mu��$Q/J����8�P+��]f�?X=�X����a�E��V����6�Q�w:�N�S1� @� @� @`�$�G|> @� @�:�X�T�� @� @�q����O� @� @��N$�;�< @� @�F\@by�'�� @� @� @�S��N�,O� @� @���X�	`� @� @��T@b�S1� @� @� @`�$�G|> @� @�:�X�T�� @� @�q����O� @� @��N$�;�< @� @�F\@by�'�� @� @� @�S��N�,O� @� @���X�	`� @� @��T@b�S1� @� @� @`�$�G|> @� @�:�X�T�� @� @�q����O� @� @��N$�;�< @� @�F\`|�����?11Q<�������+V������r�����������Y����[�Xu�����2>��������<�(1�}����8��NL;k�G�4��N�}���J�ql����������C��zh���A��q��w�����9�i�c��{���8�s(;����1����y����.m�u����>��i��v��������j�����<$u�Y�vm��cGF��:����r�5��U=Gc�v�E��8f����v9�o�l+��s��}c�{3������o�g�c�1�������;{�>���q�'�/_>��^=�������l���WUQ����������z"b�g�����&����cxV�<���N��b����}��5k����^{m[!�&��n�mu�Bh�@^��!@�F���,q ����z�����8Q��y�=N.:yS�M?�
Wf"�[�n�
q�g�?��fn�N��)f���1l���l����n��|$7��{V��3O�{�V'�f'�����,����o�=��H�E�,�D�3���}E=�2�q�I'eT�u��y�c�	'���������?����^&3^�������?��]�������h?{���A'�h���z=�q2jO~��;:����=�g�F\pA�y�Bc��kO{��R�q�Mf��,�3��>��c�4s_Q����h�\�o����u���.�����>J�'@� @� @���	H,��RE @� @�
�����Q @� @� @�g�=�T @� @�FC@by4�l� @� @�����r�(UD� @� @����X�8% @� @�z& ��3J @� @� @`4$�G#�FI� @� @���	H,��RE @� @�
�����Q @� @� @�g�=�T @� @�FC@by4�l� @� @�����r�(UD� @� @����X�8% @� @�z& ��3J @� @� @`4$�G#�FI� @� @���	H,��RE @� @�
�����Q @� @� @�g�=�T @� @�FC@by4�l� @� @�����r�(UD� @� @����ae����LOO�a���/�����e����X�<����xV����Af��Y�|yZ1?#Y%�����m����n*�w�x�K�g�����D{��M�?�����S���m�SK�5355���].��u��u�v��b�� �\V�^]&&&��099Y2����y�6��62�hv||<�<*b�y���}Wl�c��_�yH����C��1GW�XM����>I���J3�gE3�sh�P�I����X^B��>�7,�'�Qw��`���l���=��u��S��H�g&�d�_q���:��I���C���(����md����c���9}��C�1�6�t��iS���t�N��<6�s"���Yl;Y%����e�d����|��y`��������8�N��� k;��ug&�����Y�=������X�v��v�J�q�g�������~��T72���3{���2OD�C�'	3�y�0��a�;�j�����)�z�U��L���3��7\���F��;�O�Q���>1w��_�f����+W�,�V�J�S$43���_��Z��7{���Nf�+�&m�Vq����]�����Af�>G����+k.����Av�.�h�v�}����Vc�]�vm�f��??����Y�~"_�H���6���%@� @� @���	H,�^� @� @�J�F�
#�������	/���9����o�����/���q��C�	 @� @� 0��M,��_����k��f�/9��7�Y����,8	�=�\����H� @� @��(	42�����7��|�S�j�����Z�a{Xy��0���7o��yO @� @� @`�X���P^��W�;����f�V��['�#����?}��1 @� @� @�#�F}y�G>��r��WI���;���o�fK��F�3�<��� @� @� @��Ru����[��'�X������=�i����Z0�(7�pCu��O?�Z����++V��~\�� @� @�Q�F%�/�����g>s�/����o�������|�����~wy�{�[�l�R�B#��������'=i�*s�}�W����9_��sg�Z��Y!�-_Z� 0�����/�
Z����[ut����gO����p��\��n���S;��v<66���]-��:?���O���C*������;
C}�o}�[�mo{[���K�n������xE����T^���.X�K^��R��<|�s�9�:�l�����������}oP��N~D��1hu��#:���d�8����4��x����/��q��}{�����������:^=�j�*����QO���A�����5��G��l��}����<���A6���o}C�Z4*��b�G�\�_y��u��K/-��{n�L���7��
���`9�������#�� @� @�FQ`��]tQ��gl����7s=�j�g<��U��`~�;��`b��/|auK�z�������W5�]�v����Ua�k�b�W�9�d^� �s���I1�+�@��Zhu�^�j���Vo��W�n�V\A���]T��<P�z>�#�xv����>�J {;��[�DGb���9���H'��J���>{�X<��O��\�������l��9���_��9��'/����O���N`��_�>�=�l���Gb��q�N,/6^k��i�V;�����,����y1m[�?b��A�1���?��A�
K���q�Z���|y�aq�Ot"0w�����	'�P�.�m��{)6��� @� @�1���b���.+[�l)Oy�S����zD��������������x� @� @�
�+�������w�����o�3����'�������'	 @� @� 0�#�X~��_����h����g���_�b�+��<������ @� @�e����O��O�O������.�}�s���������f���>V�������3��9b� @� @��%0����������5��0���w��J9~��t�I��������?� @� @���@���y�c�UW]�`�W�\Y�����.*������m�����^��]��z^$@� @� @���
4:��IP�����'�\�t��e	 @� @� 0j��q�����S������S;�����Pv�
	C�0� �������mub�B�����)���,�&�����1�bcccO�E�����=� @���K(�q�tf��x��|�����7�d*��9�={�dN��o����p�����l���'*�������g���;{e����{���J�;�(sZc�q���K����T��5�s"��,���������c_��/b�����CV��f�8��6��A�M����Z�?s������J�7����������Q������^�@n&sXU����t��v��%;a�y2����^��d&�"��\�,�s4����3���U�Rc<99����S�83�Qwf�c;��{wSl�� d'2���OL��������}W$r2��sf���N����m&;qI��qt�����d�[���K����d���?3������G�1��g������n;�#@�� �.[���M� @� @�i�i�*&@� @� @�@3$��W�"@� @� @�@���r��	 @� @� �L��f��� @� @� �& ��F�b @� @�4S@b��q5* @� @��	H,���� @� @���Xnf\�� @� @�i�i�*&@� @� @�@3$��W�"@� @� @�@���r��	 @� @� �L��f��� @� @� �& ��F�b @� @�4S@b��q5* @� @��	H,���� @� @���Xnf\�� @� @�i�i�*&@� @� @�@3$��W�"@� @� @�@���r��	 @� @� �L��f��� @� @� �& ��F�b @� @�4S`����Qs�1����i����{�	'��V��={����Z���k���XJ��]�bE��#Nu��?������.�W�nY����?5��������n{���c������e9�y�O�-3�;v�(�V��t�m/c��iS��w�`�D�;����_��d�8����x��[��q���G�J=���ou��8,_�<-����+�/�������N���|���m&:����i�}��-�EV�62�:�w��.��)�G�j=�}
���>��1d�8s�������k��q�;���A���� �jU��q���
LMM�u~�jl����v�[�������e��I���Bc�FU��;�Q����m���j��l��5��H�F�%����}���U}Uo��DR$�D�+�"Y%����h��5�1�y���	���v�k����Wu�[����DY%���woV����������~(�|e���3��c�=��Y%����{oV�}���00�����~�v]g�W2�tt,{�	��1d��I"��e�I����]����X2����s�����u����1�G�3���f�v�����>��hw�z.u�;�3��z��o�Qv��~�f�\8�
� @� @� @�A�
�� @� @� @���P� @� @�$ ���`
 @� @��! ��em @� @� @�A�
�� @� @� @���P� @� @�$ ���`
 @� @��! ��em @� @� @�A�
�� @� @� @���P� @� @�$ ���`
 @� @��! ��em @� @� @�A�
�� @� @� @���P� @� @�$ ���`
 @� @��! ��em @� @� @�A�
�� @� @� @���P� @� @�$ ���`
 @� @��! ��em @� @� @�A�
�����K�LOO/��� 0[���v���QO���=
�XJ�_Q~�v������� ����r�V]-955U���_������w�qU���].p������Ww�v�����S��[�z�.������M7�T�����a��"V+W�,Xx�E�1���r���������+�������,[�,m;�����:�j#)�������O��N���7�'N�c���c[��?�n���j_g���fngas���?��U�q�������m������~��-����(��y����eKY�vmU�|����3u�}i���|�k���9�����;m�G�3}"Q��J��d�����g;e��}~1�<��t�!�d� {;����;�������y�~�+�w��n�\�`G�)�Y��S���V�,��x�oN���+����=��������6v�����:NF2���v�i%��U"����������4���@2K;��b��Tv�#��Yv���V}fR����g����%�W��{o�\�o�������_�q��|�1��iSj�:�����5k�,��~�$��o��{����jo����,��b_�~�=99��..�~���y�Y��������g&���i�=�-���D��~d�?�a���F?2c���y����
�&�'����P��������.�E�Q@b9;*q�j����ZW����h���a�`���qk�a_B������q��0u���������d��������p�r�{)���'��@�'Z����v4-C�@S���ZS��� @� @�f	H,���� @� @�Z	H,��: @� @���X��� @� @���Xn%�u @� @��% �<�� @� @�h% ��J�� @� @� 0K@by� @� @� �J@b����	 @� @� @`����, @� @� @����r+!� @� @� @��,��Y @� @� @�@+��VB^'@� @� @��Y��8< @� @� @��V����N� @� @��$�gqx@� @� @��$�[	y� @� @�f	H,���� @� @�Z	H,��: @� @���X��� @� @���Xn%�u @� @��%0>�������������XjLmcjj��OV��sgV�U���lY��E����o�^�����d�+VdU��z����r�������i�c��g���+W��f��]e����mdW����e��n�-���������P+��A�9B��A�6�����pu�J�W2c�U�:X�1������s�l�B������2c���w���V����0u�KF@by������W��N0������T�L�Im�8���w�N���mK�?�2O��9��4�������-���j499�:�={���?b�c���6����FZ���M�~"�1�����MLLT�d�!�5�!NV�d&��8�o����/�zcN�16���#��}��3�m�6��F����Z�g� �2}������8~�\�*a���m l�C�L�,�������2���C����G2�u����m8|�@���a�p�3�1�8��l#��~�f��_�8��	FqR�y��}B���?����;;9�Y?��h#s1G3c��y�5W3m��Q���L�o?��v2K?��5��%�����62���M���N�d�3�=j�����Qf|�&b�y��v�����;{;��9Z��o��@����n�"@� @� @��	H,7(��B� @� @��~H,�CY @� @�h���r��i( @� @�����r?��A� @� @��	H,7(��B� @� @��~H,�CY @� @�h���r��i( @� @�����r?��A� @��P`jj��z��e��=�iq���7� @� @��vv��U���w�k���\��e��}ell�����/g�qF�����I'��NU�!@�@���r*��	 @� @��	�y���e/{Y������r������r9~��?�����/-?��?xh @`��P�& @� @`�����[~�W~�l���J��O�T9����������#���~���}�+����_��/���u�Y3j�'�+����� @� @��|�UR��/,�x�+����*�NNNV����_���[��[�������������r?��E� @��C��_�z��s���9^��SO|���G]>���}�I @`�@�$ @� @`����D/��������Y�f��=I��~
H,�S[[ @� @��9�����8p�\}��s����n����K��9���>�/@@by��$@� @��x�S�R6o�\^����k��v�K����e���p�	�g~�g=�B`|�j� @� @��_��W�)��R���������y�����O.6l([�n-��v[�����j��N;������wW���~�g��u�YG<�	dH,g��� @� �������r��WZ#��u"�������7�X���r�����H�XN�U1 @� @�=�G?������{��T�JC!@�@�$��%� @� @��<��~z���" �<,��A?���{P��U<xp����������S%b��y�u�?66�6����������e���{K�(�do�}�����u�����3K?���������w�����h�v��`Gt�a?����<��ov���M��ag� �������]8�x)K4��E��@�2P�p6�y""e��i8���N��Q�S�(���/�'*��iSj�+V�����H$�����U}��W�^�VT<99�j�r�����6q�*��{oV�U���J�,��=�b?����}Q���9TO���A?�W{�����$~g��z��J�|��1������D����q�Uj��wV;��f����2c6Y���{�yx����������h'������e��e���=b�i�Yw=o��������<������������j�z�����w�v��% ��(����}2	���a�f&[z�}dm�|�Y�&;�a�y�l��f8e�9�MQ$M3? �����d�������v��!Z�1�t��E��9���'�^�NFe)�B�!s��9��'���g�?{��g�#���W;f��6�{~����{�������+�������Z�_�By�;�Q?l���~����r\���7��Z>��,�����H@b�G��!@� @�t+�=��=��O~r����~o�l\8P�w������	 �X���
Z� @� �H���E�tZV�ZU~�����,O��E4:��k���������%�\2/V�K�=�yO��vr�=����7�s�=�<�)OI����� @� @�0��������r�w��>�����!�'���r�h_����k��f�/���m[y�_Xn���J=��x�WT?�������T_����h� @� 0[��;�,������;��,�<��#�+�������������O}���+^��*�|�y������/6l(��v[y��^V>��O�?��?��znY� @� @�=��a}�UWU������P��w\y��~��? 0��%��v�~���������;��_-����K�����|eY�re���?��?-�x�3���_^~���[�n��& @� 0b_����|��?���s��j�k����R~��X�������S1\��@����G��_r\��-�u�{���������>�PR�z�;��-1��G��|�3���'�'���&@� @��T n�����5������������G>�D2����w��������
4*��u��r��'��<�9�iO{Z��E���k��#	=W����_�U$��� @� ��������xGUU$��"���P�BWd4*�|��g>��~Y�L���r���:j���������������/}i�[n����v���;l��?�/4T @������Z�����p%m���:G��(��s4��y�1v�<X���O�:f�8�?���8D����D�o��>��%n�� @`�	4*��q���|���	��W^�~}�T�����������H �U�9�����e���^��s�9�����Z >����k��X�v<aZT'�n�EUl��������}����n��z��/�������Yp���e���E�iQ����*Y`��C�B�����,b�|��>�D�	d�����V���[���}�����9�+�����;�w�{���	OxB����r����G�y�]�Q��N�bg�g��j���[���k�����D�� @� @�@7z��J�����Ju{�H,�+_)�]vY���H0G�9�
)0����b`��Ue����^m\'�'''�Q�~c�����6��AW�:���q��d����[��
��q���A�V�8�X��e[q�1�yF�v���:^����Z��?�E�.1��
������������x����v��� z5V�\Y%�#�|�w�}�C���p�
��o~sy�[�Z���g��?�����FV`d���uF$~���z�,��_�f��/�z����|p���;��s��8�\6��^�������O����5{%`;�����G��x�8�m������i����n�j+>����U����Xl�[�6��V�{��'�$��=���������.b����NZ�c$q[����M��E]T�����/����1>��O�[o��7xj!@�@��$�������������j @� @���D�:��/~�;!n����W�,B`��V����������U���>���^� @� @���?�����]
 @`��H'�/������+��iR�_����~����s�=�uO @� @� @`TF:�|����SO=�\w�u���/�5���w�-[��SN9��w�y�^�� @� @��,0��X����/(�\rI���K�g>���y��r�5�T�����%/����Gy�; @� @��/0�W,G���������%�e�c�Xy�[�R%��J����u��s��( @� @�z(��+�#i|�UW���oT�����[_�r�-%��/����|���� @� @�=�F'�;
���[�G!@� @� @���\�;��W @� @� @`W,��2����Y����;�1���������+��?p�@���N�?*^�n][�@���,�E�������b��v�j����������^�vm�ZF�o����8�mnV�Z�Q�v���<�8g���QG�U}uK�����}�*�NL;�K��m���A���v���_��^���w��������a������0���?�vR1��o�^b�N���n|����������L�,�3��v=�t��I:m��s����|�ONN������;������>�5�.jw��T�I��?���y�L�v���\��>��N��i�����~"������}]���:^�������<��G�3c�if��v�n��u|���v�n9�@^�c5��x3�Y� �w���&�Dg���i�G����8i�L�F��Mh������W���ww�j[�����y|DB0���;~2�i��F�+�DB3��Q��m���_�a�����12�u�/��f��X������z]���"�;w�<������N��w����o�1�d�O<��.�/��,��|�,������,���l����1���v��~,����m��[?��c��4�����M���v;n��n�P��g�D���Y�(s[�ws�9J�qf|�M��h
��h���	 @� @� ����r�tV$@� @� @��h
H,�f��� @� @�]H,wMgE @� @������h���	 @� @� ����r�tV$@� @� @��h
H,�f��� @� @�]H,wMgE @� @������h���	 @� @� ����r�tV$@� @� @��h
H,�f��� @� @�]H,wMgE @� @������h���	 @� @� ����r�tV$@� @� @��h
H,�f��� @� @�]H,wMgE @� @������h���	 @� @� ����r�tV$@� @� @��h
H,�f��� @� @�]H,wMgE @� @������h���	 @� @� ����r�tV$@� @� @��h
�������O<�����������7��������<������155U<X��s���;�g?���lY{��LOOW����;�G=�Qi���|��_,H��JO:������v��������c�i�1w&''K��V%�Z�D�$�_��W��7�����_�P�?����o��W\QbY1���{��u�����[u������Sb_�f�����f;���{�����������gUF���j����w�.������7��<�)���V}����;���8�S��q�'�R�1dm31��?L������_��������O��n��9���N�73��3�_��^��?�-���v=�[���x�'J'�d����t��'~2��N<�C���9:s{i�������u�O�����_&����;���o�qe���v�M���;��!@��R���-�QI���'��4�3���%V�u@?������������/���Cot2Z�>��>G2K�����=��c����J���7^i���3��E�<��W?��He���b;�l��&RgT����o�3��3,3��:���F�d�1��.�c���g�a����LZ���I��}P��.����n�n_��;��Af�4��%�E����u��M1���k_��g������]�v�3���:3��7�(����M�1 @� @� @�@W�]�Y� @� @��+ �<��7r @� @�t% ���� @� @� 0���{#'@� @� @�@W�]�Y� @� @��+ �<��7r @� @�t% ���� @� @� 0���{#'@� @� @�@W�]�Y� @� @��+ �<��7r @� @�t% ���� @� @� 0���{#'@� @� @�@W�]�Y� @� @��+ �<��7r @� @�t% ���� @� @� 0���{#'@� @� @�@W�]�Y� @� @��+ �<��7r @� @�t% ���� @� @� 0���{#'@� @� @�@W�]�Y� @� @��+0>�C���8P���Wn����
����\f1<x��OV���cY��������f�a��{�U���� ;��-+���Y<����N�����������o�^������u����n�U�w�]w���W/�V�K��/�`�/F���������d�N�Z@IDAT��/F�����g
{�3�3��A�sh������Av\����F�'�y_?555�����'@�9����������u���l)��s�����)���%N�C���y��Yw�D�W�X�F��8�,1��'�d� ��a1�|���c��O��������d�{f�q���u��Y��Vm�Z�jQ]�}��Y��a��e����jo�����h�v�PJ��do�����?��8G�,�Mf� �����q�yxf�re���f����L��������:�.vl��D�����>d�c�N�'@�@/r��������8��]����=��r�H���7E��@K1nI4����C899YZ%�����1�Vnu�I�������~l�K?F��av���X������7�E�[�C�b4_�	�����E@?	 @� @� @�#����,L� @� @��� @� @�t$ ����	 @� @� @@b� @� @� @���$�;��0 @� @�H,� @� @� ����rG\&@� @� @��es� @� @�:�X���� @� @�  �l @� @� @�@G�qY� @� @�$�� @� @��H@b�#. @� @� @����9@� @� @�	H,w�ea @� @��X6 @� @� @�#����,L� @� @��� @� @�t$ ����	 @� @� @@b� @� @� @����;Z��C-066V�'�����6�}�-��s������������>x�`����D�3�Rf�1�a���2��Yw��mg���1G��c�6����*���YUW�f�8;��8}�<s�F���T��C���63����������`F�Ut/ ���]���
G��}��|������0��c��A���l#�&����hc����+�d��0�l#b��={����gn���U�R���T���kW���{bb"�����?s�fnc1���k�vG2cI���i?L3�\�dn����}c��S=�3c�Yw�?����Cf����2�uG�Jf�����OMM�������q�������u~ @`�r3���1��f�2O�E�9��;��0���	s(�({�F�3��Yw?�h�d�8�������3�Qb�9G��qf���>��n��������_��Q�����=X��1����i����WC�M�z������s4\�c�=��9��N���
�}$<��FN� @� @��FH,7:�G� @� @���H,��T� @� @�h���r��kp @� @�����r�M�H� @� @��FH,7:�G� @� @���H,��T� @� @�h���r��kp @� @�����r�M�H� @� @��FH,7:�G� @� @���H,��T� @� @�h���r��kp @� @�����r�M�H� @� @��FH,7:�G� @� @���H,��T� @� @�h���r��kp @� @�����r�M�H� @� @��FH,7:�G� @� @���H,��T� @� @�h���r��kp @� @�����r�M�H� @� @��FH,7:�G������}C���d�?�h��=����L!CX��%] @`�	�/��p�&''SG?66�Z���t�nc��e�m��'�,_���X�"�������T�	U��\�2�gbb��<�,�1��{��L��?b�Yb�f� ��p	���A�g� s?Z���8d����w�{�=c����ee�D���,a��:�Yc�}��y��29�������2gn������~��h#���}u����\f���:	 ���3�~�@md��E'�q��n#�D*�������	y8)�D�3��]��#��+��A�z:wM���L���'{_7�\��]j���wf�2����m��_�1�6�����1d�9���F���9��&�'��Y����C��B�w�c��8d����F��';��>�&@��0
�^�7�"�L� @� @�
H,/��E @� @�8\`�o��k�������p�Y�/���r�g�z� @� @�����'����o����=���s��X^P�� @� @�����'�����*�{������9c�y��9��$ @� @�FQ@b����T~���>�s��	 @� @�FL`����n(��s������/.�'R=�w��2999���<���?]��G1�Q���������F�3�<�>� @� @�.���.g�uV����#:~���#�k�w�yg�����r��9����Aw��H_�|���������r���W���w_Y�bE����� @� @�,I�H�>�Y���oe�����>�/���ay�;�9o�����e�F:�|��7������O>�����.�}�{��-[��e������'=�I-�o���2===�rQ|�I�A���������}X@�������8��:nOMM��7�N�����P��,J�������b��x��^U�gT�������tb����o}�[�mo{[��qc�/�������W���K_�Ry�K_���S��������}j��r�]w�������Y����~H,�"o��H��#Js"�����7{_���`�����s��z��{������x���s�=m�#��k������^�&{���~6�����~�������qk�l���8>Tn�}}�#{�����#0���������+�^zi9��s+�8���ox��?��r�����=�q���V @� @�:������T?�w\�y��_�s��~��%��.����Z�?����.<��������N:���~�;b�N�>���<��O~�|��_.��~{��iS��ysu��-���o��j�x.���U��_���Kz��J\��?��?���_=��?��zk���?_=��-�/_^n���������{qS�5.�����V]���s�)�T���O\�y�w����W�x�e��3��L5�X�������}������o���x�xF��{8�se���L_���a=��,k�����a���G9��c����|���z���?������������]��b^-T/^[x�ha	�q�EU��
��'�x��qU�3���j�	����B����*�a�Uv��]m\q�f�X��N�b���w;����V�q���+f��������>kv����f�����@�v�������d��U���z���O����e/�����O�t�����r�QG�����P"/%���������q��H�n����_����Y�m{fW\qEy��^T���o�|�����N+�~���O��Oz-����w^����}my��_|��������"y	�(�|�#g��-l�'��m�J���B�0��C����O���������Yu��j��<���,��]�;�����?��7������}l��G>R����Uy��|��]��������?�������m�����C�G.������������zm��o��������'�&���g�H�,��F���?�c?V��������C�����b^��/���N,G��S���������o��zC7�-�
p�z.���7E�O-Z����e��g����
�q��Z�Xrc��m3��B�X�����k��U-�q���P�'����D5>�V'������ap#��7��/V ��lu��6�\�~}�����H?�#?R>���V+�p�	U�/������*9�S+�{�����g�y���<�9������e�]V]uI�����9�z���2�T�I��I���]7�W�W��~������c���+u?��O��}k���K�����%�{�������bL�U��N����>����n��+�#iWDG����^�_��_�UW]U>���G<�sV�������_^%`c��=eq�o�G���h�W_$�|��^�;���6���G������MozS���X5����_�U�@����|��_��j�����\�>����x�<�������������d�]��X�R��#&�B� @� �4"\'�#��~x���W���w�k���������/D����7��P�����������C���u�;Tw\�	��e�mG[����Y%Q#����}��U��wW]����~�J���������{Q��}�C����_����q����C�}���a����?��?U���9�p��M<����uu���c��T�:���H�Gb���<J\�1�U�������:J�3�O��������W��#���WV.q%v�H�?�IO*�~�6+�,��s�.#����*���yfY���YW?���r��B|�2W�+���}_�+��Z�s @� @����f�&"�S���W����{�S?�S�U��8n�I��%� }���^]�W���/�B�������C�L�$`�N�n/�~�+_y���<����,q�����%�Sq�c$*]��mo{[���D�
���d����z��?��j������n�1_����Q������;k�����[}����N������%��\rI���������c��Z�����������\�vN��O�tb9>Mx���U�D�������M� @� @���!	�]�vU�����W~�g~���#=�9�\p�%nc�S��T�+Q�g���A$�J�����m;�C#������I�����W�F�6����t����X�<���o����o��o��R\�yF�+|�b����'���9�H:��M/3o�����b�U]O?��=�c����������om�{���Q��}� @� @`i�=����wO9��r�=�����o���z�����K�+�������������8������u=�����}������Q�z��z�c��������G��D�w.��_�_�I����y���p�����^�y��h#n�]^�e��q�s��D��3���+����uY��������N,��j�=\��8�
�������o~���M��/|�����38�"@� @�8R���F�d|]|�\;%��<W�s����h�/��[bD����J\�<WYl�w�q��jO>��C/�?f&�[����N������!s�s���z���,�/6��@��|�����\I�Xw�������x�o�����5�������*����-��x�����1
 @� @������[;�������w�=�z�w��/���}������m{f��s���,�"!_�%�Z�����e�������Z2���y5���b9�c"��.���o���E�K���&�AL� @� @��Q�#w��g��}�sms���y���Wf&@��_������M��/�m{���3�^>��V���7���,q�m���n(��v[��g&I7n��r�a[`���3���������#�X������
d��]��7 @� @�����ys��g?[��wbb��p�����_�e�������w�����[u���E�q���������'�^F�bG�(KM��(��~��cT�Rl�ID5�$��56�Dl�DE�������?������wg�s^�{ww���s�gfv����9��.t����`��_�mM'��K;��c�F��M>�n��� y�r�Y�v+����g�<��l6#�3X
=����Gcu��}"� � � � ��@�N��[�l�I�&��Z�z�9����g����7�~��_���!��#�HeM��v�Z;���m���Av�X��5?olU@[�L$K��W\a]t���Uy����<��Z��o�!i�m�j��6�g�}�b������&���}��6e�����/(��r'���K��]��z\e��32b9D�B��E+�I'gp��hK��c�k;���Op���l��Q�|����oG������
A�e[��x���s�O��)F>���c�w�2��_������O#�A#.|�����������s�Z�� ��\
2��J�,e�&�����cNu��������l?��\P�l�|����/�m����s��|�XF>���}�zo���l��l���|���\�_��y�}��T�l���M��e�n��c(����K�u���L��O@����W������.��2����5l�p�h��K/���w����z���
�4m��s��_�c�n�\@w��Q6}�t������k��m��,6l���5�����Y��}c�O��������-Z��[�~��m����x#�G}��z�������ed��|��w��M������_|�4@b9r�}���n�i������_�W;��jz�bW4����uf�r����O1�?�~�q��I���_���>T�S?z��v��;�C���=����WoH:���Ge���Py�����|��\�����O���f�/[+��z��v�1l�G�U)����������|�c�i)%���jk���K��2�mr�����kbp,ez����7~}���Q�t���~�>��)W����L�M�~�l��q�K~��g?��U�\��k�\����q�vQ{�[r����4�~�%�����@�g�l�Q>Ri	�n���T���OLA��Q�����[n����g.���
��'v�~�m�HS`h�r�����J�]w]�������_��dU�
n+����A?~|��|���?p�t���G?r�5?����[o��K��C����
��5����P�X��tISx���?wY�M����X�pal��+W��g�m���2y��������y������:u���;7�����q\����*v�� � � � �).��B;��s�Z;�0�i���c����o~����J���
�3�<�jxV:������v��_u��u�^}Q������(\�)d��^���������FL�&��7����������Y�����`������KM#���|�I;��C�i�����{�z5i��0N��E����m�z��E��wo$�3gN�Mb��t�)���2T�Ym���4n�8��k���z�����E	�p����,�Z�,��*v#,[��!� � � �,��h���h�'O62���/�
�T��
���9��8����4}�g�a��F#w�����F��2�����fCi����z����m�z��a���������
��U�V���w�y�`���I#��y�;���cSQ(���Gu�i4�F9�K&Lp�Nk� �����������#���o��������[0r�M�6v�5����7=LYh�W(�>v�Xv�M���>�8�|�/��o��_K������y	2��-[f<�@�����3��YdPW����&9eQ��7>9m�Cf��W5�&DJ/�7f���<�>���K������u��9��*��:8���?.�
L����3O�����MI��k�*[����������n4��4������A#p���2]]Ju��K����K�F��}����i��;|��|��������:|��������1��}�A�>�C���cHF>����~/�uN�@3%�t��7�|�����L�Kb�F�*8f����O!�X�n�)@�d�7:Y��(�b�B�����?�>����m��#�3%}VT�Y�U=��*#�3m����BAa�L�e���lR%����]0\�{����t
�F%)(���g�R]]�q������%(@@@@ �
���{�)v*t���BSx�'��)5���o��I����%]eE�/4�F^G5���.%]�B�+��cx�oa�G@@@@�L��e��4@@@@�r����N�)s2MyWNf�h#����>@@@@@ /��i?
�9��s��7�`�rj� � � � � �@5�h���v�ZP-���vA;���	,W@'�D@@@@�*p��g�~H�%�T���@@@@(y�%�ET@@@@(-��(���6 � � � ��X�t��������{�>��S�������
2���m�r�T+f��a��v�������iS;��#m����T��X�m=�O�n�����
������O�*/�r ���[ � � � � Pt�G}��>�l[�v���U�v�uW�2e�M�<����.�������N��^��~�]r�%�}�vk���m���^x����~gO<��s�1Y�UH�\�1w�\��������iC`9+��21F~nl� � � � �@�.\h��s�*>���Yc�|��{������A������k��f�^z���W�{�1[�r��Z����>���\�YV@�\���GDW =��g��j��I;��S
��f`�r&!�#� � � � P���`��C1bD�6
�p�
6�|�8q���O�[n�%�>�m�m�6�����o��.[�:u���>����cw�y��5*U�,�������'Y�4!
��������:u��,�B`�rH�� � � � ��/��^z���O�����5kV������
�#|������ys�*�\�y���C=��;�3g�m��u�|�Z���O?�tSp��?���|����y�#�C�8@@@@�x��m��%��U��E/[��-�y�����_���o������}��U��!�b;���-_�������� ���cK`+�n�����Y3>R���'L�������7�tS�j^{`��T�D@@@@ LMy��^{Y�F�v(V���������~��|���nQ� t���>�m�@���
*������=���l�����{w{���b�3=����~���v������G���M�&f��F,{@�H@@@@�%��_����o�������'w��W_�<-[�L�W#������o��/��6l�`#G��a����8p����~.��<���jl]�'A���#Yy)��������.��X.�3{A@@@A�����u��%mI��M��C����J�0�;��N�"���k��&N[H����z�������5k�_��k��A�\Uinc� x\u�_5k��=Y�n�{���o���]}��;lr�y��5�\c������M[���;����Pi���V��N�Q�_H�] � � � ��#��s��w�����m�����h��!�<��3�N�:iK;��sC,+����T���{�G�i����X�~}�h��`���PR`\i�=���S�����4���3���X���/l������t��7�MY�k���Y������w�q��]��)�M*����Y�'@@@@��n�j�H�tE)�Z���i�j��U�����
�����p�T�����xM��r������ ��\^Msq�1���N+���O=�T{��Wv�{����c��Z�k��q��z$�	F+���q�x��g]�{�\;J���7��U��*;�p.���m��Lu�]��~�<�����e���������Qy��c_u���1l������)����>�j����1�V�'�:�'p���6d�^_u(V����m���)V=��G�"�u���IW�t������Nm����>���	�;T�l�$�l����>�9h��6�(������s��k?����8�� ��+p��g�l���R��>������:����R��l��|���}�/�l�+���g�����m���w)Y�u�Z���_|�Ek���=���v�G��� ����_��.��j���	�
*���;�vZq�A��
z'��#��O=�w�Q�
�+)XM*����zW���M�76�71�6��)�~
�<��m6y}8P�����g6&�y���>�$�]�������0G�2��c'U�|���Q.�B��*�s'��%�mr5�%�����.��U�}���m����ok>���1�^a��s>�	���<]{}^��m�s�S�>�@e�<�f����u�}�<���K���5�mr}��ys�����g�<F��\��%o���ql�c���(�IuV���c��Y�fY���g�q��*���nn�>��4�9���X���.]��� H��cG��q��6d�� k����'�]�O=�T��W������QG���E�7���g � � � ��%��� ��O>_N�������~����r�M�>=����T ��C5�~������Gq����4j������J��b����y�/�>����[���i4u6)�z��+� �����,�7f � � � �$����M�fm��u#�5
F6�����	&�n�ls�����#G���)1/^l�G�v�.��� ������>�h�<xp��zA������x�
�={�u��-X��1�z�������]�v�_��"	0F���
 � � � �@�Q�
����_�����X�d�.�*���3f�V_r�%�h�"����K�.����������`�F/�F{���4����O�����n���c�=f�����]���3g����{��&M�T�.��|���p�B�4M,��8����^@@@@�K@A��fz�#�
=������y�����/�����n��f�Z���/��F���M52Xu���L���[cEj:
�O:����l��S�����-[�vA`9���X��@@@@<	h�r��{�Z�b�y��:���}�Q�z��W����n���;����s�Z��/�����[���]p{��nj����M�����"�z�(��M3����X����� � � � �/�Q�|pN�j����;��M����#S���'P-����_6y�d�MK����U�V�ZH� � � � �e%P������b�����FC���jj.����o����^x��*�1b��k��
d���g�����y��y��R8/@@@@�Z@�(��u�����X�]*���kO>����??���O�u�]{�'�h������#GVY�@@@@@��=���I��7�q��\+
4����np#�u��!C��[o���<�
8�5	@@@@�tQ��T�z�uQ}��{����B�w�}��G5�IR��O>��_�=���_,������}�2e�M�6��u����@@@@�D� ����� P\��G,��;���������`��I�����?�\ON=�T�������� � � � � ��'j`y���6o�<��^�zUi���>�^k�N8��:��Oi��9U��@@@@@��B�
C7���i�ke���c���_|��>��C�y���uz��_����5��� � � � �$
Dq��(�9�����:bY����cW~0rY/tC��k����#��P�++������_ � � � �$�X��c�����
�X����,F�a.�u�����Cc>�=��a����C=�����#��' � � � � ��)�Tj��!C������_�:w�lu����V>���K�.N��W_5��,Y�^���nv������B@@@@ ��J��a9�}���l��_�v���y��XP�k������Z�z��XPy��wv����[�@@@@�8FP�����(�>bYg�u�u���&M�d�-���>�4Z�i��1�N�:Y������v�W��f�e�	 � � � �I���EY�K`Ym�w�}�O���o���X�Q#�A��v�r@@@@@�B������K/�������z�f)*_��v�G��Q��n�J@@@@������ce��/7���O<���v�mn
�l�^z�%�>}z�`t���@@@@@�����0�����[m��6k�,��A��l�<[�l�M�6�_|�����53�sm��=c
������+�m������ZVb~���s���m��>���m��c�\�K�}�n�:��qcZ�U�V�����v+V������W��5M?QN���j�<}AE��>m���~tm����!9�<|�}�G���k��c�w�<F���<Vu����/���^�|�%� �@)X����gS�L�����7��}���xQW^]��t�!�O��Qo�zs�W�^�6�|���s28�t,��U�i�����!������ie1�3���1��8
�:e1>}R�4����s��>��wCd)jQ
�4�]�v�����SP�����[7�g�}�k���&���Yn��������������T���Yv[N�|���rPS�!��"u���L����}>S�>����G����	Z"�U�l���r;K�;c5d�sF&2 �]������j����y�~�������������>@�CL�&M2�Z��}&]t}������������>V�����(F��}�a�����>|����}�����
Q/_��L�E�/���5��A#���O�R�m�T/��k���Q�G�
���B�������`���@6>}����G1�����������1��P����3%��LB���}L�W����:���<C`G����:u�;����|��X��>��}���v�I'����[���F5l����oo����'��2@@@@���i9�~������A��O�M����\`zNB@@@@(/����g�q�q���>�$��5 � � � �Dq�r�\pGQ@Y�X8p`Y��8@@@@@��B,W:(�G@@@�'�9���������;���/���?�j��W/����{>n�8�?~^�9���L?$@@@@@���;�<u�T5j�kY��Mc���~�&M��W����K`9/96B@@@*G��������t�,�n�� � � � �@�
0F��,���@����C��e�]�����A�8q�m��%x��c|99mHf@@@@��`�r�t5
-a���u��1�$����'.�5 � � � � �@	�X.#�� � � � ���HGQ��=����/�������j��iM�41��u����o~3���� � � � � P<�����r�M�4���k��N9�����a����� � � � ��#��5j��\��:r]F�3��Y�x�b���~g��u�/��2CX� � � � PI�tQz������!z`��'�0������&L�`o���-]��>����?�a#F��f��9��;�3�<c�?���3&6������������� � � � � �@DB,/\���<�L��m��s�=6u�T8p�z��n��:�w��>|�-Z��-W���w��>}��E]d����]p����G��?�8"�T@@@@(�������l���v����O~��������[�:u��k��+V��
4��o��:u�d��ow#���J@@@@������u����#z`y������N�
q�=��<��p�tA��w�q����XTxD@@@H�F�5=�@9	�X��e�i^d��m�f���U+�������M�-�����WY�@@@@���J9����[���B
,��U�Z�l���|�����z�-�WS_������e�6m��@@@@@�B
,���us�6l��Z�*c�F�m����l�6lp7��sM�AB@@@@@�������C��B,2��,\���=�X{����z�����+���~��_���z����[��s���������f�����}/i,,=�l��O��:���Q�����3���m���a���_�8�t0�")P�t�����>����; ����@������/�{C��@��wq�	'��^hc����3g���o����������kg+W���>�������R�l��	��y������	����T�l5j��]B��Q@'�I_d�L���[�z�E���mE(��y���]����T��>|%���:�}�<�t�<�|��|�}�c�w���3���z~���]�v��UT~����iM��3��������}���>����6�<~��}�����_�>�y}�}���*_���c((?h�������K�����}�E���,(�<�|B3f��k���ovSZ,Z����,�x��.��ys�Z#��)4���kw�uW��XV�����\�t�vU�!�s�}?AE|���}�>FU�F*�g����~���|����������!Q?w|_��7�	W@���~.��>=��W;|��������)'���H���G|����w�}��G���������U�����N�����9��c�>����|o�����=��4�e���g?�������������;�������8��H��Ui/@@@@@�2�Xlv�}w<xp���kr�7��������mx� � � � � PZ^��M�TN��k@@@@���������_X��X���N9�)�w`��^���������z�����7���/���;��CB@@@@ ��^��a9��;�<u�T5j��i��Mc���~�&M��W���K`9/96B@@@�4�5k��w��]�c�=��������<��M�6-�v����+�L�>�3f���n����}S���#������[e7��O����WY������};��S�fy�y��/�#� � � � ���F+Gq�r�u��}��~��.0\�v����]w�eS�LI��~��W������n�\r��M��5��7�fK���~gO<��s�1�:��;�~����^�{��M���
\�w`y���v�e���k�q�&N�h[�l	^��_NN�@@@@�"�X�s���k�}��'*��w�q�+�[�~���i��v��@IDATX���^{�.��R�W�����O��y��q�6d�;����������GOU�������I�&v�)������,��S�������yx� � � � ����g��{�}���V�fM��uk���g�����+L�]h�pu�n���m�fW]u�����UC1G����>�1c���w���w�}�1�$KK�.������
.w��)Y6��$P#�r(@@@@��\�F����1�<`��*k$o�SB$��`�r�n���N�L��y���C=�F��3'�����<y��q�;�3Xv��w�Q�;dHX��A\��Oj'�|r�Z^�-@`9lQ�C@@@�*L���BQ�-[f{�������g�y�Z�j�w�3g�t��eMm��3%�>�`����
8�����x������f����7�|��V�����o���:�8��CL�q,_��M��C��&Lp�Ek^��n�)n
O}	�=�����y���e�]L�OB@@@@ �@LN�����v�iv�EY�Zy��bD���M�6�	'�`/����@�FEk���8������m��
������9��s���q��{������Z���,��?����y��S�0���+W�|`
`'K�s���/w�F�mM�6M��e!�}���#F��:*O���@@@@@����C+�e���]��� �������y��)v��]n���.��bT9r�
6,V�\�o��\pWy\�&}��W.[��-Sfn �M�q����d�7_��B*�@����T�� � � � � �?M�p�Yg�oA�g��M�k��&�?�d=��c��)$J%)H�h�"W�3�<����?X��
�k-��h�����s�9��o���������mkW_}�M9�����k����~��;�I\�9����q�z�n���[�n��d���?��O�q������N�#VT�;���O��s��t
M�������c����Ck�������~���E�g�}f�[�6M>��YH � � � �����W\qE��n���[�
��f
q��~�+���[����#4UD)�F����F�jj��j���~���d���}�{���s�������6u�����T3f�p7�S`��/���7��W�o��yl�������'X��W�^����F^k�u�$�xy�5>
_]M�}�u��E�_�]y���c����\v�e��_����c�^{�������s@@@@�l�����^���H/4��~�%�K%��Q�
�@�di��w�#�8�4�{����,pY5��1��l���`��SO=�^y������\`c��uSWh��PN��u��MF+k���9�S���p�,���F*/\���8����r������oM�~���Z>��sS�r@@@@�
��ZF���GG��
.+-]��=j�e%�{������u�A�Ue��A��)&�����_��'X�[�j,�=�����`5�����o!2�u4S�SN9������@�G@@@@�dQ�&kCu.{�����g�����%�\��*��Vi���v�;vt��f��!�y�_�F#]�m���jM���A�9�f��.�]�fM���:=����W��z�:���U</�@�_�l���f��������M��u�I � � � ����������4�����aG��-s7����&|�?YI�J5nb����;����o��/���:�k��|�����U������!�#�<b�7�����91M�>�-JtN����B
,��U+v�FM��m��:�tWI � � � ��4Z9�?���s�SO=e&L��|O��
�4�����=��
���Q`��5v��'���������>�h<x�7��������7�0

���K�x�����#G���)1/^l�G�v�.����E����ny��]��g�_�����7�>l�0;��c��T���w�}�[���� � � � �@:��H�Su���X�h���h]�tq+5���uv�	'��)S����c�����t�>�P�������)���c�����k�6����������{�I�&U�K������{w���e��O�b<����d���$-B�yS
FS'��Bo��XV-�9Vt�@��L��
}��oD4�����m��wf~�x �#� � � �� ����?���L�;SPWS_��7��[n���i|��g���n�t�F+��`�'�|b��z��|��n���x���-U8(#�Q�'����6h� �(e���h���/����Nv�F��V��,'��u�#�{��e^x���w�}����g;���i��v�����M�����a���:�/�\)�a`/ � � � �DK�o��It�����>�Y���O�t�I�n���ys�M��r�
[�nm'Nt�gh`��G�\�m��	���X�^=7��w�a������C�H7�Yu�`UR�	�XVSn��67Y�0h���+W���3g��RM�������++lA��6�d#��(We�l}i���M�H�G��du��u���\B�ci�]K������LW��u�������c���Q.�P�}����}�k�	�����u���������=�b���v��[7Y���������,[6j������Y�N��q�}�C�W����1<���`������]t�<�V����u������q���	��>�\}�qp-����O�����#�>������c��:�|����i�s6�����W�e��>�88N���|��R~>}��>������l����U��Q�-�M�r�����;w�e��y���������!�%��[s,k��h�5kV�G�$��<�
�����F�G��BC����AG��7k�,� kT���T����w�MT�)�c�t�/�T�}���__��R:ntL�1%]s������K]�f]�D���������a�\�J&���(FX�v�zU�1��f���.�c�g��d��TD����QTJ�-�.�����>���Z���\)�t��:V����������R��J��r<�K9H��;�uN��# /����m���9Y�M=����[��h� � � � � �@��~��0���3����d�\�B@@@���F���������ho�:�����w�@@@@rP�� m�nl�@�%=b9��R � � � � �@��X.��@@@@�(��Q�s��]EP��r;�*#� � � ��*�T������,�Z�P@@@@��Q��:��VV���"k���3faO���������+�q��V�N���H���i�&[�f��[����A�E�s���>�����������^�z��aC?;*�R+�<��,XJ���=�����P�*�B�~�c�I�&�Z�P�����m�������C-�T��K�g��W�������Y�%���u����]az/�7o^x{,i���K�S4#���R*�
X�U,���������yl�& � P�W\qE97��!� P��0l�����k�����*��2#�#u�Q�,,g�TH�_��6x��B������T	���A�TB�����������q P~���7��SZT�>n��u�^�{�����O<�]���
���;�UA{����\i���%P����<�5�U��X���.�,~�%��i��%_��
F�}'�uNt�5���5<<�u�]M?$@@ ��+�:u
^�� � ����is#+�,{��X@@@@?Q,G��~z�R�E��r��$�@@@@*@����41�#�MT@@@@ ����(�9���d����@@@@�$��Q�FI�-]�,��a]�wFQ�:#� � � � �e$z`y��
�m��2"�) � � � � ���O�1|�p{�����O�k���4h����������[���vdF@@@(O��(�~�U������0���m[[�d��h���-[f5k��x�B@@@�`�������#'p��'�9���zSaR	�:���[������W�=*�Rg9 � � � � a�P����o�q��������#� � � ��*��0��S����|B
,�7�p�5i��>��s����?�������!� � � � PE �c�F�����@9	�~��f����w�iW\q���/���:w�l:t�=��������O���:����Y� � � � P��H��)X�Z�Q�L�������I�b�]�j�M�>����x2b���,��g�z��-.���} +�B�5��Jh�������>���>.������;���<���v�Z����S�.��A?T�{�:.h��WZ�+�����3q�g����w�z�m���]��s
�m��J��������6��R=�\j
�����7��h����@O`��)��]��|��������y;6@@���bO�:��+W�^�z��1c����S��X�b�K�H�v�-z`������7���F���]�o��>��u�]W��,�~�6v�����qc�[�nAeEa�M�6���_��5l�0
�.���1}\�T��������r}�����8�>~����W��U<o^��t��m��6*�~��i��T��z����5����E������k��qm����c���R�XR-[��,�[���u�����
�4���
�`�%i:�(&��Q�5�\n���7o^nF�G��<��rJ���l�2���(�Z�i��
���_�f*��V�{����r;����
TD�������XS}��:u�d���7�(�d�P�U��J	���PXn��M��K��g"��>S�����>V/���.���jC�[�vmW�n(�)�����7���Q,G��Q8��c�	�XN��%�p�B7��U�V�4'T*-�#� � � ���bL)�uN��r$P�'��9s�O�>nxM��Q��;wv�v�yg;��s�����Y�F@@@(#h��SF]@Sp^�[�l�+���:� {��'l���;p�X�����n;�����[n�a=@@@@H&��2#���$��,�e*�o�1,�Is��G�n`��{��u���O>�w�y��}�]������3���%uG@@@�,�=���@ �@����3g��JGq��;��\NV���z�.��[�h�]p�v��'���%��2@@@@X�
�������B?��c�7o�����3�<�2�������\���us����g�/�@@@@@�Y �����P>|xV���v�j�
r�������_ � � � �$F,k�r�~���7Ye�P����u���;�yt��=k� ��^����W_ym��M��������m����6hmI#��m���������Z�2��|��
�:��������)?S9���.��W�Z�����}��6l���e�M���8�y*�`��P�v��e��������U�>�|�����C{.��5kz�c���G���:wt��&�&���)+Y��n���V�L����j���T�>�X��^�:��88g��z��ee��ukk��eVy��I��z���t<��������sL�����l����?��R�y*-]�4�]�~�P�����j��5����� �s8�:��N�:Ym������l��>>���c�c�Q;|%�F����y|�����>�X�s��v[t�������\�2��w��x��eY5Uu���sVy��_@�����g��Xg��}�����o����Pg��AE�i���nR��|��L��������Z�fM>�f�M.�U���e����<M>����ZVO��^���U}`��5j��B�mv.m��`��v��Q����I�&��\�ms.�Tv>��<���?�
B�R� �����
���<��n��yR��,Y�M3�����R,g{|��� (�������� ��)o>�u\�x�{^�q3�I�M>��L�c����/_FQI�P�L��)����~>���z_�ym��>#��V��c}N����=���}|~A���i ����}~��5(������;��r>r���b�6�u����\�N���S�N�e��iY�L�:���o������ � � � ��'��S*��hq��X�a���F�a}�QF���'�n�w�Ae�O@@@@@��=�|��W��EDs��������?'��#���u�]g��r��w�V8p`�j�w@@@@���h�`��(=��$�I �9���.���Q����.�����A����/�������sO7/��l.���9�����
3�u��+���v�k�V�ZY������N��w�9����l���6c����/�C�v����'���MI+�B@@@@��Q�F��i;��/z`Y�^x����>�������}����O���c���0��x������nr7���Z�h����o��O>iW^y�w�qU�����g?��>��-�i������s?����
><��w���@@@@ /h	��E�F�*�%����6{�l���;�����o���3�N��`�{��v�9��2*�_��W,��2��[��u������^���7�l;v��v�-�x�����������k�i����4��+��bc��q#�c�@@@@��T�QK���c�7�����v� �UW]������}���SO������w�H�`�
.�{�������F4+�F(+��;�4��~��v�
7X�z����m��o~�����=���6x�`k���[�/@@@@@�������off��������J���������+����Ae��?�4%F������
.�@@@@JC@1�(����@ �#�SUQSML�<�4��w���{��f�\SV��}��5K����+����s��q���s��
,O�>��}�]0`@�j^#� � � �Y@e��(2:�C ������-[��������/v�%�����}�1�F��t��<n����������k���'�O0��k���U
p+��c+��7��_�\7���ys���s���$�����������:��>.��o����3�o�]��U��s�������M�6U?J����~�����L�g���W����2�}����,����m��e|������K����#���)�=��$�I�K`y�����_��9�x��������]w]?]t���>�k��LAg���������N�������_���
,7i�����6Lx������&,v/�����?R�;��V�=�������}\�=��+A@_gz�.4���7n��/���~�s��^(�:|������.*���*?��Y��GT���$H�_�5k��w��]�c�=������~��v�m��������v��G����w�}�*/�����f?~|V�����o�M���X~������T�Z�jY�
b5�
�t��Y��]|��v����Q�c��ugM���[�X�0�<�������/���\�
ho����"���5j����> � � � �@�0��@16���M�f�k���cn��v7�����K��^x����~gO<��s�1y���F��c�������>�]�i���rVR�e
=�|�=������>��u������O>��_�=���_,�|���oD�L��N�0����hh������� iY����7�����:u��%}���{m���I��C�a�h�"������/��s]x��4t��*P���4!�����o�-�ZHT������|)��9l���������[W} ��M���3�}�d���w��/X�5��*�T���@kez������K�J��R��k��'�|2�*���kv����A���O7��w�aC���N:�����FC���,6��=z�0�N�*)���4�)���*�C=��o
��:��XPY�'M������<u���z�)����oWY���w|��7����wSPx��a��g��k���i�d��@�,o��a���ex`�y����X2�����77���@q8�����*S@�Y��};�!��*'���9��~x��[
���c����a���w��L��2�]�R��b�O�Q����?���{������YR
v���Y@�����*�������\��>����cw�y��5*SQ��������'YZ�t��^h�Vp�S�N���,$�P�R�H�y��������J������N8���]v����3gN����P0��?��*��	
�OTV�
,+d�"��n����y���<E@@@�N� ���0�x�;���]PY#���"q���M�<�`�8����,�����(��
H+��C�����'�]h=���A\��Oj'�|r�j^�,j`YUp3��_DU_-{��]�=���_|��[��&zne�����l�����];���~���r�V�Z�u�&Y
�w��9�j�!� � � �Y@����B��-[f{�������g�y���V������n����m����r�!��N;��m�t�IAdMm�x����<��W�������g����z$>a�7#��U����W���@��e�F�](����z���]�VO-q$��i��w��=��K��5t���n8������ni�:����z�AbR�\��+���"q;^#� � � ����H���a��v�i.�{�9�4��~�����;��V���>��Q XA�Y�f������
�jJ���g[�����������$�z$��9�/��r�x�����i��,�� j`Y�;���]5G���������CcU0`@���
�M�4l^I�o���z�){������@���{�i,�`��`�:1V�X���vX��G@@@@�E`�]w�Z�
�eZ0�k0Ml��h��R�W�:/��bS<o���6q�D���~�F-����_����q�F�'Yy��e�R�d�(��d���FQ��#P���PO�5R7�{�������u��F+�x����K�����j
2���4�X����t�j������'+k���6���o�4��n��!���O�:�����:W\qEA�%��@@@@�Pl��c�M����^�+�z���n:V���O?-Vu2�'��X<N�A0e��*���K������mkW_}���w�yv�5��k�����Ow�� �z�m{��?��=<xp(��X�<I+z`Ys��[
l7o����k������*�z��XPYC��.�;��
�{�h��*7�K7Y��-[��4����m���o]`Y�@sAk$���������@@@@�>���������PX������O<�vw
�*(^
)�*b���)���W���3w�\������S�n���g�����U{u_5
ML�5r�`���e���;n� ��6�x��Uu����[7�4i��d?���M����Ey:u�d�[�v��hTp07����TV�:��:� {��G���}����\}k"x � � � �@�hJ�����jW�����I�T�RI�2Bi���)���y�JVI�s�1)���`�d��~��Wv�{����c��Z�k��q��z$�	F+�����#O�K`Y��7�I�t�IM�QJ��-Z�~H � � � ��)��q)���U*f�;S�����_~�2k�m�����T���w���B�8�4��A��y��`��|�_������J
V��+�-���:�J���T�b����V�u.���j{��k���	_�Q��<�I���|���3>��M�6�jZd����1$��5kz�H7�O;�i�O#|]�����W�j��>�y�;����?���G;��R�~��+�����}���:�}�7aY�*G��O'�A�����d����3��zo�M||~��>�c}�]����<Fu��}�|�m������<����=\�>�E*��y�k���+�~�����L(�t����|���
��6+V���K���� H��cG��q��n�� o����'�[������#�@���v5������_��"�X~������wU��������=7n���??��w�q��JM�����������Y�����]���h��I�s}gS1��u���+�}�6l��}����&(7��@�:�G}��v�*O����1���>�u"�7���y�9��<FR�t����u�-[�,]
^�>�{����r���I��U}|��|�������g0G�������5��>�?����W�/���P>�Q�c��c��l��4�����W�Z������>�O�$�D���g��j���YY�����u�����M�����>AK��
�z�����o�s�=g'�|r��k�X})w�a���CV
f&����/��-[V�F�74�Y���n�)�t�8�z��t����e��_�s�y�5���Q�\
u�
�?���[9��k�h%��1+�m�F��������X�u�t��SJo���E1�S��P�:����g�s�����k���GmU��g�w�/���9���w�:��~��6����%���K;���&���{x1�_��B�`�
|~>���)�?�����{�V���>gu}�|�����p�u��%V��/��N;�49r����ys�n���6z�h���K/��W�����G���^�������o�����������7�p�h�{-��k=��}������]��/�y��,�~�@@@@�������`�A��\r�%�h�"��������o��ww�`�^���4���t�E�(�T��n���c�=f
T+O���M��9s������s��?��M��#({����i0�:X�cq�,:�.��2WK�4�����3g�?�1����<G@@@@ �b`����Q�/���]x��n���7��x(�����L���52Xd�(O��[o�5�w�>�O:����l��S���$��!���t�y�,k��d�<������ � � � P��X�_����7��i}���6Hx�{I�}��v�w�{������I_���[��``�����+�M�6	�g�2�z(��s
��k_�9�,�"��������IU_�#� � � �DK �q�R��F)|��9�j����;��M����#S���'P#��/��"�����p�
��g��]<�!� � � �T�@0b9���m4�B,�Hg_{�����{�	'�`&L�
6�!MB@@@(�A�b��?v}*�A�������W_u�����0�4k��h��s�����Ua	 � � � ��4��n���x#�����"�(���~����i�����#G��{����j�*���;���3�Ar����t�����@@@@@��B,��k��l��a��C���k�����v�i'�z���v�W�n��f�{���{�6m�l�# � � � �)�
#%
+(����r|���o�������]Y�����g[�l���~����om����'�o�s@@@@�D1���JCx�@��X����c}���G}�����]w�e��7w��/_n�g���� � � � �@R� P���
a!��}�,4�����b��)�q���&����=�	 � � � ��A09qy��V�I��@Q�
?��36~�x�Ln����v�i�����?��r��- � � � �!��Q�j��r���S�I���������m���v����#�<b�$}Cs��G�`��[n��A��G@@@@�
0�7-+(�@���y����q����O?��J#��c;�����������WY�@@@@2	0F&!�#P���?���m��I��k�d��OS]{���7J1� � � � ��!@|)46A d���A��w������M��yD@@@@ o��8_1�����
KT ������n�G��.]��h�� � � � � �@!����R�E@@@@ ��F�Fq�o���X���,�������;�^�zY��=�s��o���y�w�q� � � � ���e*�d2,C��y��N�j�F�r���A`����r��\�S�n]����@@@�@�(���b�+����9�X�ad-�m���~|�b�����R����������|�C�i�������}�>���>�1�{����[�u��-[����>|�����x��>�n������k�r��6��n�|�����o#_�W�A|�#���\��
��7��i��u��:�|���{|�j��v��������	�\���9������9�[-��@xy��j�]v���Fi���������U�c�n��X��6o��m����Y�&����(�o�7n�������k�f��s>�q����
��c�<�T���W��AD�M�6���+�g�*[}�3�:��<X�z�5k��[T�_|��|�,_�����ct��
������[���\�u��1��|����V+��:gV�Z�u�|2����>��?�|&�}�c��g4�����*[���������qm��9A�}~~��>��bO���Au�ye�>�U]�}���s�����Q�X�>}|~��5�'Y�z����u%�����\�N�Ob�_�~�"^g)�;�V]��n����>?��� (�6*��9�}�>��>��v��j�����:U�g�]���W�}��G^���G�	�|;i_�R��
}�W��j�= �����u}�(���f����=Pe��v�C��7�������}����2��������>����]@�e������������^�zY�5�������6��������M8���@�5��JN@@@@@,���!� � � � Pl���X��(�b�-���@��[�t�R����Cm�.��bm��	�L
C@@@(/��(���5��;�|�]w��#Bm��>|x�eR � � � �@�Du�2���9i��,� � � � �@���b�6�u.v���h	�X�����o�>ik?�������=����;�<�����k��t'�O?�����o�����>���[�<`�;wNZ@@@@�@T���&�w`��0�$�����u�]�_��v��WZ����d����{}�e��/~�3f�]{�������J>^ � � � � /��ro�����^�y9�XN�x�T^�p��q�v�5�����k��o�[�9s�M�:��Z>��s�n�J@@@@���j`9����=�hy65���K�W^y�e?�����L'�)��������YmC&@@@@@��u���-[l��Y�5�[9���eK�u����nB>@@@@�
`Z�
�x�]R��k��e��5�+V��3l��������Ms���m�U~2!� � � �T�@T�� ^��k9�:��09��5l�0[�jUF;M�q��w�|G}t��d@@@@�\h��S��F��Q ����!C����g����������w�[�f�]����wo��y��������v`b � � � �@�@0bY����#��:��e!�T����]x��6v�X{��w�_�~��N;��\n���m���>��S����m��
�C����O[�F���F � � � ���~J�W*�e��\=�����n���@����m����r�J�3s��Z��/}�Q|�a%@@@@@JN�K`Y���9�
dS�L�Y�f�~4�E�6m������[�>}�v��%C�@@@@JO����'��2����m���g���@@@@��,����&�5�Z-)@@@@��/����Xg8�	�H��u � � � � �$
0b9Q�� � � � �%+�{{��Y�d���b�XN%���
0b9�=G�@@@@@�j`��g�m�����[m�����D� � ���-[2�oo����j����r��
���$�+P����v��}�bi����U~6���Gi�B�j���i�5	�r ���7����U�2�)�7������?L}�q��}^$���|��}��4�y�Ro��9��3m���N�:����^>�j��l���:��=H�W�r��T�O#����|�|�>:�H����}���W�U��_mk��	v�����m������k����������~�b�
����~*$�z�����������7��/��zo�������|�7j���u\���+�3��M�|����?���y^�8��������5�����W������y�>�}-����]������){�����[g�/����N�<��9�g���L���,������A��uN������y�Yo�F ���Q�=V�r}����[gl�_|�1O!�AJ��L������|}��!@e����c�g�Zo�>�@u������B_�����>�|���3x�>��/#�}P����>���>���>P?�L�Z������Y3W�|�8�k��E�}��������}^��>��������>�����|����G�>?;}�s��g(��6�|�}8���������>�}��s���Y]CW�^tu���_�}��3T�z���-��Q�����]�}�/�~D�@�����e'@`�s��R�&������x@����e���L���P9����;[M�!� �W �{������>J���Z���9>J�7�K��P�@@@@��	D1H�:�C�Q$,G���4 � � � P��X��~���'@`����!� � � ��P`9�����n�}��W�����A������6O��3f�m��f����5m���<�H0`��������?��S�L�q������b]�t���?�=�P��ef�9
@@@@"%F�6R
���}��wl��1i���g�����~�]r�%�f��A�n���/��c�N�$�����w�=��@�!+
�b9 *��01�!��D���!)�0$�H1F�qP	�D*�U�@#�8,���8������;|m�2�;3}~����jvf������}��oz__}�����`y�3����z�d'y\v�e%������k|X��?�������@IDAT�w������/��[�����YE`b��=L� @� @`��w,��{���X����.*����������V��O}���U�*7n,��^z���k��FS9����<�|��_o)V73u����_�h*G�����|��s�=�mo{[#����u%��l����\_�	 @� @�z(
����F�O�^���j,����\��_�������x��W\Q~�g~�k����w0�u�]�wF���o/������z�-�I�]w]#������_��_=��h���-7�xc���k
��O������sR	 @� @��^�j,_p�]��wo���?��W�K^��cbU�����,sss�<���Xn����?���,�}�{��������p�|��4��}�k��?��?~�*~�����w�q�s����ro=E#@� @�H�w�NLL����w,����/}�K%�U\}�^������mk�3�i�[�	OxBy��w��?��?\��G�|�|��_=��h"���P9��s��^��������|v��Q������y���iq��n���cV�����n<���=���<�[���z�F� @� �(P��r4���������zg�uV��������ZN8���u��r�y�5�9�j�����z��V]�z������h:��_,/x��|���W.���F���O~r���[����N�x��_�w|���W^����������7��q�m���_��_h�z�w)�����-N� @� @��h,����1�4ou���k_���;��C�N:�����|����_��_^i�c��gO��O<������1U�.--��.��:t�����o�[8�����w����w~�w��������N�_��Y�#�%��>����g�Q^�����MH<�/���h5
�u(���:�� @� @�@���'�|��+��eu�5g�����<��������5�o�d�X����������?��H4|��O����o�Fy���U����4�M�V���qLU�x�y��8p���'>����O�<�1�i4p�^&>D��~����>���|^x����{'yTA>��O�;����G�h*������o������X^�����F@c�7�� @� @��A`��}���Z��fk��4^+���EC�[�����{�+7���N���w��/�v�����K�Z��?�������icy�������?s��������c:��3�M7�����������g��������.�����eKy�#Q:�#b����L��>P�����k���<���o�"���|~���_^��W�?��?8z�~����r1�"@� @��h�a��<�Y�>z4b��M?��?_��������U�j����c��[m�������~{c��o��<���\m������_���xg����_��������D�s����o�sU���h*�����SN9��b��~���w��[��%�a������sR	 @� @���C�&''���������%���)�i��ne��rUc���^���cU����~t��xxL�T�����������'=��T������;f����7�$�����k,��g<���r��xG����������j��J���5�{o*" @� @�@�@���m�����_�����������s�=F���F���U�ZM�����Nk������evv�T������g�����{�m4��&������q;��/���u����]k�$���rL6lX5t�4h���-2 @� @���
D���_�*\w�u��'���o\1�?�����|h^|�]�Vc��]�������w���������?��%��S�^"�����>��y�?�!q���>��������V���<v�����y�[~=�c���g{���:��]c���� @� @�$�����;��~�1���������z���>���{��{������#�������������~��x��_�����}Y~K�������{��W��U��������f�����5n�q����p�W��M�����r�,j������Oz9��3���<�[tT+�������t|����W��z����H@� @� @ G�j*�D���������w�>�Y�*]tQ���X��1]u�U��~����+_��r��w�����[�g���~�/xAy����h����q����?��r�=���=�y�g�g�?��E��������LOO�h^���}����w�m����Z���G���=�yO������w��|���m��y�����|�����=�������V.�kO@c�=/s @� @�P ����1�n��X������+�l�������[�+��������r����z��������W��\{����l���(�����o��o�|�y�5�/�����������b���s�������C'yDs�_�B���K����c
�h����q9��sZY�y��X��� @� @���kc�����;���+^�������������O|b��}��E��V�6n��x������4n��'�&�Z�8>����
7���s�r"n��J>���W[M��;�#�}��O|������v�m������x���?��q� @� @�=���j4��	��)��|�-4����=��f���|'y��1�CM��X����k��'sZXX(�6mJ[E������W��z����A�_�n�z��Xm]�'��_J���)�G����w7��JV��{��'�<�v��O�=�����Xk�*v+5�y����q��*N�YS��Z���>�7c�~���Yoe����<�@����L��c�9��Rr���J=�E�bk������4��R������Q���:�f�#����6�I�~��[�����XO�9�1+���5E���:]�����+sss��h�\�;����o�]V��8�a��TYS���V��v��G���r�!���5�����[��8�3��sS�~�X�o2�c�'��5��e�8��Y&�7����EYv����(	�u?FI�Oc��c�M���+C�����a��[i��G;R���d^�DC0��?j��p��aCK
����ay,{����q���N�O9���:���]��H��������uE����^�=/��N���4�!^T�>�Y���a��R������]$���KA9*h���9j�����6�������M�>M���5xv
�n�]���:�!�������{�����T^{��k��>8��S�N��g�����J�J�_�w�;v��>���g�a��s�
�-������ @� @�F^@�v�Kl�5�X�A��H� @� �O�?M2��\�s�-����@3��fB�'@� @�*�:�c��9U�%3t�CW	 @� @��&
�:��Wcy��z���u���	 @� @�c(
ZM�1,�!������DB @� @��	x��j2'�_���z[ @� @�@�]�Y�@&zK( @� @��X�"" @� @`T�z�e���-�8*��J�w @� @����������yt�np����-`��w�dO� @� @���x�r���� @� @�S�x�o���V�V�r�*��<��� @� @���ul��1��=H�{�6 @� @���D�V��6���h,�pq
� @� 0j�T���0|x��m����l @� @���@]���]����$����r�Pf#@� @�M����,�[@cy��o� @� @��Z	DS�������f&�4�[@2 @� @��p��A[������F��a��� @� @�V��&��4$�W������ @� @� @����/� @� @� @��n��_�5��������>����m�5�_ZZZ��^<y������7�����.5���@�����u�4��x~~����1���R��_��LOO���^=c��b���?+�*���L9p�@�k��gn�=Ov@���3�5���~�_W^�G+���&j���j,Y��?@irr�d���=���8�?���k�����)��/+�~���F�}8{�6�>�@��h���f~�#q1��������l��no��fK�I��H�ylC�M�0��A�w�qU)��g����o_Z�8����,^p=���LC�>6<�@Z�x���e���i���3��YS�g���8�d�k�%�u��R�y���f�:���e2kU��m�D���(sq
�?��?{;����������Qf�3�Ma�A��5�������l��)��}�����:�:y���}q��I@c�N��+ �.��8�$��fN'9��2��Dv��w����0����N����q��� ������ @�w���;K� @� @� 0�cQf�$@� @� @�@�F�Vq/�W������O.�{��VT�y���w��\��s������?���w @� @�����6���Mox����������q���nXs#��c����B�$@� @� @`�F�����{��{���onZ��o��1�\P���g�8��g����$@� @� @��8
�\c����l���+����[����k�X�������5��$ @� @��2R����|�\~�����S��������Mk�����s�i:� @� @� @���z��C=TN=���������O�D���������|�����`>��������l��������$@� @� @���
�Tc���.*/x������u����^�������^�������������q�x�%/yI������������hR�4����,,,��{���t_�44����v}�������4=o��9���qw���M���Q[�Z��y�����g����"����[w8���A�f�����n�9Z� @�@oF��|��'��R�_���Fy�;�Yb����}�k��7����s��\���+��������������?���s��}+=����O�}���(��+����j<R�\q0j�"K_�sz��v�X�4���h����T�����j,��u��������`&P#�����rv���G)nv
"~�������s�����r������u����7������"N��������x����/,�x�3�
o~ @� @����X7�/�������}{���U��/����Z����^�fc�w~�wV��>���{��r���W�W��6s�q��i���cg�[k���A���oj<�o����y{���]%Z�9����!n����6w���\�?[����||��g�g����R���~��]]������D�svX�|����&�$@`����/��=��U���g?���������}������}�?���4��L�H���6�
��_���������N4;o��)b����q����:t�P�3!F_~xGu�l:��eF`t�=^7����l�������0j��� b��Iz��QX�S:J#�b,'�tRc������n�.��( @� @��*0��X�������;��_\�<��c������c��m+��f @� @�|��?�����~�����-�y�{Vd���������w���{� @� @��(0���g>�����c+w�y�����[J��9�_��_:�9� @� @� @`���V/|���>��������e/+\pA���;�(�������^Z�9��q�F�� @� @�G�ucyrr�\u�U��a\w�u%��_1�v�i���.+^x�`~!@� @� @����tc��Oz��������������K�=��Sv��U�:���e��5��$ @� @��U`���ujj��~����v�3/ @� @��M@cy�*����:�����������?��n���ud:E��S?�g�d�T�c���2��C�v�������������'����G
2��3}"vf�������r����f�8``�D!X {?�������������(��M���F�A��^h,�Z��x�'�����.2\{������3>����v�s=��-�^���he66�/��>{����5����V���4���7o�q�G��c���;�|�������D���C�v���������q(l2}�`��<,[����=����^G�����.X�~�y\	��g�G��0�l����J��W���~2����y������{������sY�������r���A���d��q�A�,\�s4�3��DU��n���rfS6�0
5�jQ�����4�c��o���g6C���_��V�
������������qm�y��>�!�P-���o���*L� @�E���D���� @� @� @�^����l	 @� @� 0p����@ @� @�����r��%[ @� @�\@cy�%� @� @��%��\�z�� @� @��Xx	$@� @� @��z	h,��^�%@� @� @���4�^	 @� @� @�^����l	 @� @� 0p����@ @� @�����r��%[ @� @�\@cy�%� @� @��%��\�z�� @� @��Xx	$@� @� @��z	h,��^�%@� @� @���4�^	 @� @� @�^����l	 @� @� 0p����@ @� @�����r��%[ @� @�\@cy�%� @� @��%��\�z�� @� @��x8,���p������K|eM���+���Y����b�u�W��:T���v������������Y>�
2�G
8P��������y���} ��q��������������x���{������l�x�� �Z��]�;+�T����/�X]O�u��{�f�T�3��g��^�t+���Y�T�f�����udn�s;�/�7;�v<����r���9�8�f^��3�N����cD�:�-����w��	m���s���������ZNx�3���������z1�_^��x����1�k9)��A;r=~kA �B-V"���r��B���h���j�����,q�\] ud��� _#��OE}������^��
����yQ�w���F�?����4�f��F�����V4�������sAV����m��~����������jp��e����a��:��t��1�7;�V����_���
�+�v�����Sv�;��D�yu��:�6�y
[����j^�����5N�Q����1g����������
���@� @� @�=�X�9�� @� @�m������ @� @� @���='� @� @��-��<��5: @� @��\@c��� @� @� @`�4�G��FG� @� @���h,��T@ @� @������h��� @� @� �s����
H� @� @����X�� @� @�z.���sR	 @� @� 0���]_�#@� @� @�@�4�{N*  @� @�F[@cy��kt @� @�����r�I$@� @� @��hh,�v}�� @� @�=�X�9�� @� @�m������ @� @� @���='� @� @��-��<��5: @� @��\`��<B`ii�,..����#�/���X[`~~��y{nnn� ->;;;�t]-F3[��k�,���k|��k�����Av
"~+�����J���q�XN�v���=�P�5�_��d��"�M�65���6l�P�+k���S�jj*o����(���KF�#��3��h���Y�����W{�'����?uq1;99��\W
5��F:T�l����{�X����W���L�={���7f��8'w�qi�c�m4��:�e�;w�lz���wo���cb�������+�����\*��
#k{X�oe���^���W9���@v��?�Z9b?����!7Y:�8���\�:�$3~�_3_KD���f^CE
2��ur�������e�M��	���H�t?����F��'��4X�����M��)�gNq���7�b0l2���}fc6���5���D�������������w_U�����hlfM��Ey��y<����cz���������q$�Y����+s�z������m���Q�/`���?������fns�_f��o5�\��	�~�Cj�rL�u�q��Y���}�����!���S������'�q�9�������m(��y>��f����5�k�V^�Gu>�����Ec9y#�J�X�����$<�z����h����?��A�k�x��B�;-K ���&S+J�!0��7;g����]G� �[���+��<E#@� @� @��!�X�BH� @� @�u�X�K��I� @� @��!�X�BH� @� @�u�X�K��I� @� @��!�X�BH� @� @�u�X�K��I� @� @��!�X�BH� @� @�u�X�K��I� @� @��!�X�BH� @� @�u�X�K��I� @� @��!�X�BH� @� @�u�X�K��I� @� @��!�X�BH� @� @�u�X�K��I� @� @��!�X�BH� @� @�u�X�K��I� @� @��!�X�BH� @� @�u�X�K��I� @� @��!�X�BH� @� @�u�X�K��I� @� @��!��<��]����T�����uD�y�XXXH���KKK-�!�[>�[�n������:��A�x"�(�<xp��{*��
6t��KWun�f�333��,����������"k
��������i�fU�c��.�A�!k��o_j��of������h���:F��n��o������{�M+u���2��a�=E��A���#~�-��[+�g�T����ZG��L�v|���jN����J|eMql���z��$�0j�������:�q,�j���;��G
2�077���k�Nj�y.��f�!@��0h,C��C�g\f����}A#�S\He^0/���G�8�(.�:��z#���t��XI�~v�����T�|�������'s?��3k�3���?�����6m�����_�>5~�K?�n�����ki]��M$�y���q��y
����T���S��G���?{��ou����{�I����,����V���@3cG>q����������:���U��y�<b��:�8�e�����o���qc�C5�F ���cCh� @� @�/������ @� @� @�k����P @� @�@w_���K|�:�v�i��O}j����=�X�9�� @� @���n���r�5��������Zc�e-3 �!����*& @� @�
���>�<�9�9f��`�]�v��|�;���~�_X���'3� �O��~j[ @� @`���E�[[Ds�����R>��O�����^!�� �?��?kk"@� @�t,p�)�����5��(��:�cA�B@c��b @� @�� p�g��[��/|�}X�U @`u���m<C� @�*��n���������U^�!@`��cy�jn� @� @���	��-����U�:t�P��W����r��c��U���!���e� @� @��!��}�\s�5k����N8���o�����~"@��4��n� @� @�����o/��~����������������t����K|�����X��u @� @��+�S?�S���0n����������mo+oz���������sH��}��� @� @�z#��'>�����-�����
7����� @�C���,F� @���������?��r�-�^�� @���#8�B� @�^����{��o}�[�����X�2$ @� 0��}KKK��x�������w���eaa�<���]u^O @���P� @� @���^{m���k����������G>�7�Y@c���VG� @��D`��M���O/���P����v�2����r�("@� @�t&������E/Zs�������'	 �O��~j[ @� @`����_��}��������p�	e������3.��<�H� @� �O�v�*�z����7�\���s�%���{n���K����z�q? @`P���_a�k}��
���Pv�Hh~~���Z] >�6{�6�1d�#>E8s��?����[�2��?x�`J�~�O���sf�~E����?�85������\����3��;���v2H�g��R��ql��A���q��F�]����G���
eoG����q��W����T^������#[�li��{����O�|�_(�z�������j1�	 0���������������Z\(����<�<�}�/&���{���!��sss����3Q����.���x�a4�2������e8p u?��4��vjj*�1���Mvc6����C���L�8Nd�o�����R�?;l�.����ke�'bgn;s���3}��>��g�#��y|�fMf��o�1k
����������~b=�8�-O���3k�h�q(�8�G�B��5��F#�x��W^�h"_x��%��|�Yg�
64�Q�������__>�������-O|��I'�����G���4�[�����8�_�t'��������~��G����^��1s���@��^�������M���G�<��=s���~�~��c�Q���f6��'�� 3v��1{�n\g���|���*���P��������|�\t�E�?���|����8����W���r�)����Q���������<b>� @��^]�S�� @� @�+�u�]�G�����+<���^����7��o������X�U @� @���w�}��36��E��#>�����_���	 �w���S�������i�7��O>���u�;��e���Vo������~�<�������.;v�(_|q�}����G @� @`L���'4���sO�q�C��'���)0��X��C��
o(��zky��W5���w�����������WU����4���F�jR� @� @��J ���;���5���w������k2y��>�dc��$��o��)������o~�<�)O)��Y>��6n��?�����d������1�@� @��F����+�}�c�M7�T�����[n)�w�n��>�W�����7����}�+[�l)?�s?���,K���F�Vq;�+����{����'�~�+_)�wW6m��88���cz�cS~�w�<���/����������[�v�- @� @`%�
64zqK�/~�����ozz����^$z1��'�x�1? @`#����|�#���/o4����������'>����?�#?��D��3?���,O~��K�
#��& @� @�@�@�"�������o�+9�U5��?����g<���]�*O{��2��-	��;�z���
�_��������h�������/7��&�JS4���o������}������f� @� @�g�x�#��������={�������&��H5�/�������LM�6������~+M��q���n������4�������Vz�����F[@�G��1:5|��k�����A�o�f������@��W�/���V��~�����:�����$����G�2�Yv
���NB�N����������u����{�����t|�#@�@'�u`;�<�e�������YV
��S��m[��j����~����D������?������������s/Op����ZP����<���z�����9e�u�������z�]��\�xU��t�k���b|�V�x��5�#~V���&P������\����h����Av���X�#^\\l�6������.��v{��5�\S�Y�y���[t�y.>���|���K�i���F�f%@�@��H5��!��}�p�i�����I���v��� @� ���}��W^�����}�k������������g>��r�W��>�����!0�������i���u��q�������M��h~~~�yn����me�����Z�������9��<��b�5�q��j<L���E�s\���������LU�7o��t]�x�S7��a��3+�~����mYc������X�8�xX+����Q�f�1����\�'����������4~��^T������;����h:�x�����`y�k_[�������`�E"@�@�c�X��uF�?9�+M����o��%/y��O���c�������}Bcy-��"��L+��3j<�:D
2@j<�Gc��y�j,w[�x��l]�G����ip����Ff��@��rg����W[���/�]������V��A�9��9;r��:���/���T~�s�[.���#������������[���od�X>��/�Y��#^��X]uO���|�:��Wc�O_5 @� @��n���F����ek����~v�O�����[s>O @ [`���~���w�u�������{���{� @� ���������m����������@���uc���.j~��=�2�g���}����;�y� @� @��^	���������~��_����w����9�'	 �-0���/���y�����o/�����~�{�[v��Y�8�����<����B� @�����_\�>��r�UW�/��+���e���t�I��/~���x�����������Jy��^W���7�����m�o�������P���O�k��h= @� @�@�����4��o~{�+_Y�9��r���������z�|���._��W�|��W����3�_��_��~��x��,��n,�����������X���?^�+�x's|
��Z��� @� �(���e��:��\5��^��w�]������}����i#�X���M7���IOzR��������7�Y�C�N>��211�w
i�f @� @�7O{���c������4L���H7��E<��J|� @� @��8���J|� P���TJ�ZXZZja.��Y`j�9������f���=~z������>���U�}��������YS?����_q�����y���>3~�!��_���z�?���d��G�u�m�w��#;~5�	 P'��!����\j6(333i��>�f�`�P������/Z2s����������W�#�{�?t�PJ�:;;�z��Of
"�:Oa399�:��}8��`j*��>��z�M�v���=j�y����N�c����x;�?�:����e��c��>�J����^'g��'��[�g����������ci?����W�R�����&8R ������[�'�hj��d���q��}������,�,�����>�}���w<�V�?�d6O������Z�q��u3Ol��/�c����������aXs�����2�C;3~�m��uM�~?����~��������h2j9gW���Z=2���������z.�ey����XO�~���������:��u��tu��\	 @� @� 0�CP) @� @� @�N�u��\	 @� @� 0�CP) @� @� @�N�u��\	 @� @� 0�CP) @� @� @�N�u��\	 @� @� 0�CP) @� @� @�N�u��\	 @� @� 0�CP) @� @� @�N�u��\	 @� @� 0�CP) @� @� @�N�u��\	 @� @� 0�CP) @� @� @�N�u��\	 @� @� 0�CP) @� @� @�N�u��\	 @� @� 0�CP) @� @� @�N�u��\	 @� @� 0�CP) @� @� @�N�u��\	 @� @� 0�CP) @� @� @�NSuJv�s��uk�O<��2==���]�v������qc��m[Z�v/--5Y�n]��NL��-g������j9�vg���Y���<P�1m'����r�Yg������j3��S�#s���}������<�v�:;;[N;����/����{�����;��������v}b�����Y�8Ng����������[Z&��G=�Q-oCU�[��#�
6��K?gj���INau��:�AV.����������V�u��m��<��S��������O@IDAT~���?��8��c[�~�r�U�����v�j�UW��?�g�v�F]=�h����S�����V]#~�k��%�gjj*u���-{�x;�6m���b��8�\�R�f"@��
h,QQ��G�f�}A��z���@�_�w��0,>�F�|��E����Y��-[J4��_��r]���I'��d�v�/J����Y��yO9��r�����ig���V9D���3��~M���	GS3��t�7onk?h1^t�v�5��
u�O��t��h$�s�j7�������1�c�V����mu��?���>�,��w�����iE���������Y���c�/|�0��Df�h�f�����6��u����h��9�3�ur�k�a��s;>�%@�@�@��'32� @� @�*��<P~+'@� @� @�@�4��W3 @� @� @`����r @� @��O@c�~5�1 @� @�*��<P~+'@� @� @�@�4��W3 @� @� @`����r @� @��O@c�~5�1 @� @�*��<P~+'@� @� @�@�4��W3 @� @� @`����r @� @��O@c�~5�1 @� @�*��<P~+'@� @� @�@�4��W3 @� @� @`����r @� @��O@c�~5�1 @� @�*��<P~+'@� @� @�@�4��W3 @� @� @`����r @� @��O@c�~5�1 @� @�*05��������J|����4�u���4���$����X\\lz�^XX�n%�[:��]#D>& @`m�~�jv�������%@�@�4��������\y������OL=	�I0�$M���x�_\OLL��`���MM7�5f���M��g|emG������F�,�C�b;��*��1D��m(\"�L�8oLNNf���Qv��)c�|emC��C=����{����:=�T�=���M��q�����@�|���1�Sg�����9f\�z �[��c�j9�>�������y���bLYF��G�Y�#�C�Q?j<5���:���T���g���[y]�u>g��h"@�@�yg�V3�����x�#��4��>�7M��������.h�Hq(��`�������\Lu��������e�B2��������9e��}��3��x������ ��5�1(3~� ��;3�p��uk����-[�*Qu���m[�u�6�i��o����?�'��=e^D}���S�A&������K{3�����C�~����ov�����5���b���m({�g�gQ��c��������0���<�m*>-���\�8��W���D��m��/��f��xqS���
64]W��4����Wd�3�v;}���P��_C#~��������y%dH��8	���qR4V @� @�������P	 @� @� ���^(�A� @� @��1�X�b* @� @�z!���E1 @� @� 0F�cTlC%@� @� @�@/4�{�( @� @��H@cy��m� @� @�����r/� @� @� @��	h,�Q�
� @� @���X��� @� @�#��1*�� @� @� @���P� @� @�c$��<F�6T @� @��B@c��b @� @� @`�4�����J� @� @��^h,�BQ @� @�������P	 @� @� ���^(�A� @� @��1�X�b* @� @�z!���E1 @� @� 0FSc4��������(��fgg���|wA�X:3v�vff�,--���p?��[�n��l�]'�^�&C���:�T_XX�~L��}��d�!3v~�������^��~(�<���3����?���cWv	#���K�}����P�5����m(3v�e�#;~�k������w�����m
�'�������~4+�Q�����;w�!.�w�������(�},��0{?���H�������}�K�F(p��<
���q��U;�5s��������qm�������{��:T8�?g��&���q��C�6�����j��uT����8e�"~fc�����^���xQ���xjJ��hs� @��q������~�����1d������W/^��+��d�8;�`����g���,�-�v����aT*��8����Qyt��,������u��=�1*�A@�b�l� @� @�����r1�"@� @� @��8h,�C��� @� @�=�X�!�P @� @���q��1 @� @� @���=�� @� @�� ��<U6F @� @��P@c���B @� @� @`4�����H� @� @��
h,�S( @� @������8T�	 @� @� �C��b
E� @� @��q�X�*# @� @�z(���CL� @� @� 0��Pec$@� @� @�@4�{�) @� @��A@cy�l� @� @�����r1�"@� @� @��8h,�C��� @� @�=�X�!�P @� @���q��1 @� @� @��S=�%T�KKK]FX{�������n������������E����eb��o	���������g��~��#d���~lC�5�1d��W��9�8�i������sss���w3����n��G�:������z��>�e����t�R��k�T�g�2����5��_��w�I@cy��5
'���8�g��F��]�R�����233����_u�2�[��}?��?3��P��=��u�:2cG�q���%$V���W^�`�1go������w���
���Ce��}i��q}����=~Zq��4�} ���?�d�L��/+C���F��SQ'@���
h,����M ���M�L�� ������i����/�����)s=�F��k";�L���g�b����mh���lh �H$j��d�?:g^d7����E��������u�?6���k���
v���������Y;:�����l��"@� @� @��.4���8 @� @��M`�o�q�����w�c��?���-������� @� @���o,�q���nX��;v��X^S�� @� @�����7�o���F�/�����g=k���}��+>�A @� @���������T~���7���1 @� @� @�-������FL��sN[pf&@� @� @���
�ucy~~��u�]ejj��u�Y�m`��=efff\��&@� @� @�@S��������277WN?��r�u������e���ebb���K^���c?�cM?��O�����;p�@��C�����c����[�PO^ZZ�i<��O@���&2"@�~qm���=;;�X����cv�u-,,�q�2���#�1��Q��,��R�#8F���G�f�����c$�gP�V`����}��(�|�;��'�X�C�����5����7��}�s��+�X���x�+V}������8�<���k��'O8����t3C��2���f�������0GQ�a�NorS��8v������y{��}��������R���~��2==���,��@�~��������5��?U�n��5X��F�em�v�Q�f���7���\�q1/2���\�_y�����o~s��cG�:N��������x����/,�x�32� 6 @� @�j#0���K.��\t�Ee�����SO=\�xW����������|�����X~�K_Z�~�+M��v[��al��y��=F�����SN�S�x�p�����������6mj���Vd��T��I0A�R@���,=M*����{�1���k��lv}��Gv.#ZB�"@��c�X�w*�{�������~v���w�}w�����d����~�J7����K��q��m��S=�t��"�%'Sx��]����q�������kM�f����;��h����eK�u��9���>�t[�f����l����FP��g��;���[�x��]����� *�Z�`��c�������Qm��:���KDcx���m.mv @� @����X�c����/;w�,_|q9��3���}���x,�*�n6 @� @� @��w���8#|��-�}�{�{�����o����y�����$@� @� @��8
�uc���|f�������w�yD�o����h���~���x�/ @� @�g����_����O}�|���//{���\�����;��?���vq����s�9g��c'@� @� @��c�X���,W]uU�v�]w]�w)�WL��vZ������^x�_ @� @� 0�c�X��o���q��K.���s�=e��]����*[�l�m��	 @� @� ����7�+����r���7���|'@� @� @��c������� @� @�4���fB#����BYZZJQ�^�n]�+c%e����1�gnn.�hvv6-����9���������������V���?���f����q���Yu��yg�~����q"n�5�6�i�'c��NOOg�>3j0LS�q1��3��?��9���2��&���������H:�Y�5��f�8��2��?�������R�g�#l��ZOF-2�+��� �3�����S�V����m&3~�oZ���{��S���2��u���IA�=h����
#v��[~�I��������������B*��'���2X+N����"��m
������}��^7��|�?o��!�8y�6�y���P�/�2���i��n��������6���d��z�B��c{���@V�����8�f����P�Q���(M��cu�Tu����B��&j���Z�i���:�N��^	����WY�C� @� @�C#��<4�� @� @��!��\�:�� @� @�C#��<4�� @� @��!��\�:�� @� @�C#��<4�� @� @��!��\�:�� @� @�C#��<4�� @� @��!��\�:�� @� @�C#��<4�� @� @��!��\�:�� @� @�C#��<4�� @� @��!��\�:�� @� @�C#��<4�� @� @��!��\�:�� @� @�C#��<4�� @� @��!��\�:�� @� @�C#��<4�� @� @��!��\�:�� @� @�C#��<4�� @� @��!��\�:�� @� @�C#��<4�� @� @��!0U�4eY����2;;�����B��gO��dL?b�[��i����#�oe��ML��=gqq�LNN6����������5�u�Z�oL��8{j*���plC���-�~�@V��Y�ne?[��8ZY&��G����cU)S���j�3k�PL��ky�c�������)����7�.�l����_����T�k�O��W��N�_k�����<�s��he;���&���3�"~lG����uk���i�[�_mK�|��z�k'n5o���9s;�>��S����v��V��\��5�<G�0��qf�����[b�d?n�:���D����N��(
#.t��@3����g�m����)��5�d�O�<YS�8.�������?���?�G��h���2�xQ=77��p��d�g�n��n�������C����?d'��U�N��h�~����N�ow�~���G�2�-����k�8ne{c��G
�����?s�d� �]��ou��8G�Z������q�����ue�_�)�I�����5�M6��j.��=_v�c}����<W�=j�y.����jc�8�] ����>r� @� @� @�@G��Y� @� @��+��<��7r @� @�t$����� @� @� 0���[{#'@� @� @�@G��Y� @� @��+��<��7r @� @�t$����� @� @� 0���[{#'@� @� @�@G��Y� @� @��+��<��7r @� @�t$����� @� @� 0���[{#'@� @� @�@G��Y� @� @��+��<��7r @� @�t$����� @� @� 0���[{#'@� @� @�@G��Y� @� @��+��<��7r @� @�t$����� @� @� 0���[{#'@� @� @�@GS-e�����J���Bf$@�&��y;������z�1��U����� 0h��AW��	6����,,,����r���6]�	'��t�nfX\\,�O��3O���W&���+��5E
�?�ey�L�j=y�Y#j�?�����g��:d�9���Y�#���x~~>�1���c����?�������y�Z��,�7on�Z���������K��N9t��j�����g8��U+	d_�d�����cc+���Sm�����+����?��a�5�j��Af���k�����6�U��v�Q��c]MNN�pR���Zy]�}NJ���P �UJ�	��bqq'����7Z\(d^,������p�d:�!.�������-��.�-��\���M����2/�"����A4N���5E��F��L��?.j��8fe������}��d�h������5��*�,����f��f��f�U��-[�4]W��8/���4K�������]g��73��2�G����~�#s����m��A3���V�������q����e�����zf� ���m4j�y;==����q�����������r�~�T�B����k����`����i	j?C�8�b��@@����/R�plv���aC#�n��i����:x�`��/>�t[�f#���l��'0��Yv�q�Q�c��A�ov}c���['� @��y���Y�E� @� @�C#��<4�� @� @��!��\�:�� @� @�C#��<4�� @� @��!��\�:�� @� @�C#��<4�� @� @��!��\�:�� @� @�C#��<4�� @� @��!��\�:�� @� @�C#��<4�� @� @��!��\�:�� @� @�C#��<4�� @� @��!��\�:�� @� @�C#��<4�� @� @��!��\�:�� @� @�C#��<4�� @� @��!��\�:�� @� @�C#��<4�� @� @��!��\�:�� @� @�C#��<4�� @� @��!��\�:�� @� @�C#054�H�����*�����������B�L�u���L�������g������>���b=u�������T��m(5�������x���]�8wg�4;;�nJC9���3����[�}�5������i��������q�#�����A�������,����������Uk�����������ud^������dZ�q��=e_�E�����?�?���m(����Q��)�����2}�k<==]2}��d6)��'�|�?�����gnBm��z8p���Z] �
<���m�5�n��~�����#v���
����W)d�#l�bW��6�y������'�����P���I��g�G�?������^^g���'{�:d+��q6n�C0 @��2��3����q8�B!{��P��.�M�XG?��/�!=����w'`R���XXo1�A��P�5}���G�(<�bB^O4D�gbDEA�F4$x!5 �$� (�!7��_���gfvf�����o=���Y]�����wj��nc������J�^Q�
���^���^C~�N���/��|�n$/�~��a]�]~���kL���8~�[�s�O�����R�A)��g��]�R�������}��g�z��������6���%����_%&_@@@@@��
X.+?G@@@@�'@`9|mF�@@@@@��
X.+?G@@@@�'@`9|mF�@@@@@��
X.+?G@@@@�'@`9|mF�@@@@@��
X.+?G@@@@�'@`9|mF�@@@@@��
X.+?G@@@@�'@`9|mF�@@@@@��
X.+?G@@@@�'@`9|mF�@@@@@��
X.+?G@@@@�'@`9|mF�@@@@@��
X.+?G@@@@�'@`9|mF�@@@@@��
X.+?G@@@@�'@`9|mF�@@@@@��
X.+?G@@@@�'@`9|mF�@@@@@��
X.+?G@@@@�'�$|En�%�n��|�����e���#����������6m��1�l�bM������m���e��e����n�:W�f��YMMMVu��~�/�+V���r����UUUe���F[�nu�d�:����_uuu�E�z�M�6����x�����U+��c��~����l�Xe�?�[�h�U;h?��~%�W��>���e������u��X��^�������k���R�e��~�?��������7�u�����^~��k��q�����T���l^s���U��kT�m�����I��6����������[�n����Y�a������2��}1�6�{c���#��7n��ul>��^���?6��t>������U�}Qi�����:*�����_��~��jc��
{g�Z�re��:�6�9FBH�/J�x�����`Y�����u���w���c�A����B��x,���Y
��X�V��R�����6�n(*�����x��r��y���n+���`]��X�(?R~�.��]�7�~����u}�:+����;�}�@���U�J�����q�v��~B�Jjc�5-��w��o�@���x%���U_�Ji�@��(48��]3\�� � � � � �@!��c_@@@@@�,W`�Se@@@@@�����/ � � � � P��+���2 � � � � P���B��@@@@�@���T@@@@(D�I!;�ov�~���?>��C���m�l�����Ek��iHk�}�7o�l���s;4k��jjj��9�[���qH_�i��}K�_
=U�y\�6������r�8q��o��(y5���D"V[[�"�\���VUUe�[�.j�A��6j��\���l��M� �m\��Y�~��l��-����/csZ�j����54d�%h������7�X�#q@���w���RV@�R@��|0����@U�I$�EG��n��z�����2[���'�/�K���g�m��
�vW��m��*���m<p�@>|x��k�y����K]��j��������/�p���	'�`K�,q���2eJ�� 5�~������i��Z��X�J|��wpM+�j'�x�}������~�����PK�F��q������� ��=��b�~'�1����WX��?]/ ��|a�o%��6n��N����
'�;���[���Aic����3m\N���6.�s9�B�S�c#�@C��}
�5� � � � � P�%@� � � � � �@C ���Z�� � � � � �% �\d� � � � �4$�
�5� � � � � P��H4��8�%������i�\���k/���K���1�����6n�m�t�R�:u��(��
���R�7�x�6l�`�7��}��X���o����_��6.�i������"�/m\|SrD�� �\��N�@@@@@��
#o:vD@@@@*S��re�;�F@@@@� ��7;"� � � � ��)@`�2��Z#� � � � �y4�{OvD�^�u�>}z���m���:����YL������n:t�#F�-�����g���S���+�s����G����{2|�YQv�l�X�<��C�����N�N�:��
+K'�l�2?~���3��,Yb�����;���]�v)�y����
��Q `@w���W��>���~�i�7o��l���u�f�{�������������`��S�|���q=��B�XN�bR	����i���Z������rZ�@��D"6r�H�1c�5i��-q���v�%���\=v�a��?��~�L�b7�t�5m�4�u��Be���g�v���,�'T�uo����5���_�>��q����|`/���]}��v�q�%��8���"
��QD��d���W:�=������6m�d~������[o�8  �����1��r�����@5�<v�R:�@�(Jp�L�(��_|��=t�Pk��Y�rl��vu�� �
H�F��w��X�����.�|�!���7�h�[������_oo������t��3f�%������g����Y����:��:����y���>��{�z#�3��(���>�����+0�q���"��Qd�2g���}0�k}����:�(��e�=����k��c��oE��Z>N �6�n�9�=@b'��>�<`cR$����4-��7�|c�W�6��;��3�]�_��������l�����Q#��m[�?��SS/��������y��n�]w�����N����M�8��b|�����+ric��i�W�O9�����f/0a��S�O�>v����vTpy���6�|S�%m�o(q����A��P��e��;}�QS�����G�J]]]��-Z�zA*�|�E��F6Y �6� Y0���\�6���mSJ����}�o#J��q�}�
H�(F�����]q�.���W^ye�Y)@���W�XP�-����|�������`���*�����9�����>r�S��TI�������<��/�����_���7���W<+�p�	u
�-{��]/�:������
�=@��)��s}�y�77;"�N��2/�H�����/_���l$��.��b�\s��q������[��3g��^�*yc���{�c�>��+�k�|���/�8�����

�@
���v>n�8;��CS�{on��Ml=�q���"��Qd�2f����Y�f���rG���K�.��L�V�r��H^�|�rmc��{���S�G�����8_m�C�_��0x% ���wQ�H�v�'�[�nu7t�i�5
�A
�������������B��)����{�����c�<����y�l�����{���|���LO�0)Zv��g���_��p�:�"UG�=����~�����8F�D�x�(2h���G��UE�k��q�i�>�,c+���������������8<�J����r��9bH���>��c.��^(����
l��Iv�9�$|�:����b�m�6���@��[�\�r2R�V��"o�����^ �6�n56��?lUUU����7����?�C��08R�x�����Lc��t�I�{�'�q���"	��Q$�d����L�+��h��"�����{�8�O�{}�*s���):�.@�e��9@C���������
���y-��o~�5j�({��s
Z*Rp�P?}x����|���n=�&8�P��n��:�{�����2�����{������sL(�X	�~���L?�i~�u���D�<���/_y�(�}����Y��]h�w��]Kh)<�����+i����y\��@���3�.����/]������K�:���#����r_��C\?�po5C.�UMM��_�>�x�^@�i��!�m���s�5}=�u��	C,�\����������?n���:��z�F���n���w�+(�q��	x��5$Y�l���t��MiK�]#�+���	��{���[|���>�v���ZL#��0F�f�Q�
J��,������|2�N;�d��us��0R���&�4Fb��-�.LSm��`��Y��]���%������;w���+)8�(��w�A_��}����	�$��G� C��������K\#��	�r���N�J����q*E�!��,g6b�h����N�"5,����9L��w!��xI
S@)�W�7�f��i�j�sRC����n�C
Y��W����<N�����Q�2"�����5B��������Y���:$�q��l�)@`�"��J�*�������>jO?�t�]����n��vK�
+�)��0����-W�WR8tn���n��T5X�d�[����7�f�}Y���n�.��2�0U�����o��:"�q*�C���b(�3�}e������i��U�|�r7DO����W3�B�HIE�����8	�Y@ K�YB�Ye�X��~�a����m��yu0t�0s�L�|����������J���j��hX�I�&�����l����m�x�	�R��N�<�-��N�S�ez��5�\cs���}����5\Q}���>�"��G!z��W�������]�����:�y���m���n�-Z�Y���p�6�/a>�����L#��X���=*P@�6m��.V������-[b
z��m����v�G����J&����j{���{8�����`��?�s�=��CIX�Lx�=�XWX}H�`e|�6mZ��
���/�W1]&�	&��3L_C���;�C3��8�����#_�����g��*��#�$<�A�d{��'��3�8�aT�k�=@�=�����8\�Li@ XM�UJ�@0�7on7�t�]y�����M��5n���z�-�����c��v�W��� ���*<x��1�F�e�����+�
li���������v,���\2��O�2�
�0h� ������={�����%�\�z���P(����]e�\�t��v�i)���N�:�o�h��X
$?x��C5<yj\w
�5k�,���L4��z���gu:���wx*DI�H��L����q����!�@�,��(^p<�@����l�����a��q�p555v�	'��3_sN{�$G}��u�].��@�lTOf}���{�b��J(��n��v7���cM�GIC,:����T~��s�&�
������o�h��tR,/D���B�����_C��A�7������O�!C��1��_�����h�B�8������)P�j$�E�TW@c��/�5bT���V�K�Hj=��C����������-��+W��{�m���e-�G����J�����~��5��n�t}��e��i����6jR�8��@�E2X��j@@@@@�D�Y&z0� � � � � �A��r V#� � � � �$
XN�`@@@@@ ���@�F@@@@H ���� � � � � �@��X� � � � � �(@`9��9@@@@@��3�@@@@@ Q��r�s � � � � �,gb5 � � � � �@���D�@@@@@2X��j@���1c�����|��G	�>|xl��M���;Sh���7�2�z� �a���vm{���&T��5�6�����:�M�k������z(�G@@�,�L� ��Y ���~�Y�B�aY��o]�t���e9>E@@���d�)["� �@�	TWW[����Zm?�,j+<3�^���I��^*����%Kl���O�@@�@q��SoJ� �Y�z����b&?�,f�*=���Z[�~�/~��K��@@�
0FZV � � � � ����r*�!� ��{�=�:u�-]��z��iGq������t�����_�m:� �P�y����-P��h��5s���'�IDAT�~-[������V������ukK�g�}�)o|>���/�����?6s�L�e�]�G���[7�����46�u�V�6m������m��v�e��0�w�}�V�^mp��k��ml�t��!]��._�j����K6{�l�q���#�t�o�(}��m������!��v�-�����B���/���v���0_}��-Z��9��K������mz�xI���nV����{�L�|���]��u��~���w?j/ � ��H z�EB@�,��g�E=�P=�/�'\��u�]�G}4���?L����+c�6n���=����ec��M�>y���/v�6m�4
h���������z�D��C9$V����o�>2a�o���+V���
^F&O��dc��|����<��o�L1��_>�7�|s$h�S����G���H����SN9%!�h�<����^����I�w4y���#�OV��������.��X��cz����+W��3fLD�������y���b�2� � ��
�c9zGBB@��
L�>�z���
�^�x����z�^q���g.������y��� ��y��)wW��q���u'�|��1�r����(���>k��s��[����VO�������V/�o���T�����n�����'N���������������^�����6l�!C��u�_~y����CB�y�\x��
��=5��z�w�z]�|���}��wy�l��>����e�������z��]��^�z9�\2W�d��w�����j;�����z+?��s6h� S��������U'���[�v�
<��N�~`��� � ��(�o���@@�\�\���z��s�=	E���O#��iB��lz,+�hP���|����|��h 0���/��-����\��._�<��x��w������jB�����+�z$�������H4�Q�e/���<�Hl�������������O+_4��+�I�����c�U�\z,��������?~,oM�������>���s��t=������cy�r�-	�i�K�.n}t��H4���~����=������#k��IX� � �_ �{�; ��W`��I��jp�e����^�P�!�^������C��y����4���+9n��|����_�<���_��:��(��#\�l�����2���OgX�������C]��m���Ad;��cb����\��s�=�-�;w���1#��u�e����Q����8v���T��06p�@oQNG����X�z�D��	�G?4����',+����/���kY=�����V�4����������i@@(����z� ����k��6l�������kg�qF�u�-�P
z`����HN������+��
g��]�|�������N<�D;������M�Ce�hm���Ob��'4�F|P9~�Z��o�����4�0����h�d�����
����N)������0!)W�Y��M4�����^�!F���V�Z����<��E{��)�Yg����P:��:�@@
 �\0! � Lo���	�V�K��O��EY�{��5������Q/f"���6H1Shy��2X��.g~�N��������&�F�\H����x�^��y�7#�/����L��3��-����Z������KR�l���9]�����uK�:����?�1���;��cj���?�����X��;������ � ��X���=@�����������6~��g�m�����O��2o�lV3�Thy������� �`�t?�q�c��,����m�'jjjb��K�K����'�������]���X������=?[���~���:���-[f�d����];;��#���owh,���@@2
X�H� ��S@�W�\�/u�����i�i����Gn}|`Y��2e�[�moem\hy��s�����R��1�sM��!��%o�_�����N����2h���6�����o���R����w�1����@Q/���������������3 � �d'@`9;'�B@ tzP���E��-�z�����z�jH%o�e���e�u�����;f�[�zuV?w�yg�e��a�u�������]��=�r|�9U�2�O�O6�Z�haZ�(k��{���N>�����~���/�?��O�d�6 � � P�����@� xC\��7��bfZ_��'�t��'���O?���;��=����u��n:�_���s����|����rz�\��f����+t��:���'S�fZ�\�x�/��2yu�|��	�9���}�.��R{��l���v�-��r�^��L � � �@�,��@�@�~�\A/^l�'ON[���_i�eZQ]]mt�=��s6}�t��:�z3g��[_hy5��7|�K/�d�c{���*����z����x�g���:d{�t�u�Q�^�J�<�L����O?�y<�=z�����������r=��n�f����H$�M��&Lp�����z�%'��5�\cx�[��Xr��0� � ��	X.���@���g�i^o�n�!e�UA�B{wzd�R�q������{�dShy5jd�_~�;��l��w_���]��F���/���u��%�v�,,��3~��@;�W_}�&M��:6���x�����wy(p���%��+W��a��g5�}(����gi���M�8����k7�tS���:v�a�N�+@@@ o�y��# ���g�}�/��+��o�i?���m��%n^�W^y�����2��K�~���A�vQ�R�s�9���%��
l������
2_���n�:7�q�F��5F��%�\bm��u���U�:Z���������)��b���s���U�V����k����:�L���l\p��w��~h=��p�6u��X��w[�li��������/����q��[C_(=���nl���7�y��x�����l��in�O~���:&@@@������)�"� ��O?���]�\e��:t0?L=���m���6t������ZVF
&4(�<-�z�>��S����n�j�F�2�vU�d�YA���~�����v����U��v*�����:h��e�]\P]P�]�v�v���`C}p�Gd�]�6������
9��?��}`��gO���]�b�`V�����Q������G���g���^�3g�tR(�����.��2W'}����i��l���n��!CL?$@@�W������� �@�~��_����j���se���/\@Y�Ga�����! � b|��|�-��Gy�}��'��
*k�e=�OC`(u�����UO^3�H����2�������|^�f�����I�}���\�9��(o�����i�j�����5���{��
C���U�'�|�z��eM�6�m��YnZAd��ZSox�DW�Ym�^�
����������	@@(�@U����OG)�!�@� �� ������tz�]�S���`��T�[�P����S��������[C(X�������i���;����]��^��y��
��3�}�j�
}1o�<�?����1�75	@@J'@`�t�	@���"h�l��>��M�K��U`Yc _{��n8�T��@@�-@`9��G�@@��	t���f�������*��5�sl���C*M�4��=��:��@@�/�$�U� � �@�4lF�#�)���'��4f��^���O�X��}�p
4�u�]���1���K��,�� � ����ry�9: � ���;�\HRp�S�N�dQ����������~;�����k,����=�/�! � � ��������� � �@X�v�jk��-��z@������^{�5{���l���6k�,7����s�=l��Av�E���Y�F@@��
�c���@���m�l���n�:LmKRp@@r ���{ � � � � �-���kO�@@@@@r ��3; � � � � ��-@`�����#� � � � �9X���@@@@@�� �\��O�@@@@@��,�L� � � � � �@eX����� � � � � �@��s&c@@@@@��,Wv�S{@@@@@ g�9�� � � � � P��+���= � � � � �������@@@@�l��.,�d���IEND�B`�
div_var_int64.patchapplication/octet-stream; name=div_var_int64.patchDownload
diff --git a/src/backend/utils/adt/numeric.c b/src/backend/utils/adt/numeric.c
index a6409ecbee..30b0e339ff 100644
--- a/src/backend/utils/adt/numeric.c
+++ b/src/backend/utils/adt/numeric.c
@@ -554,6 +554,10 @@ static void div_var_fast(const NumericVar *var1, const NumericVar *var2,
 						 NumericVar *result, int rscale, bool round);
 static void div_var_int(const NumericVar *var, int ival, int ival_weight,
 						NumericVar *result, int rscale, bool round);
+#ifdef HAVE_INT128
+static void div_var_int64(const NumericVar *var, int64 ival, int ival_weight,
+						NumericVar *result, int rscale, bool round);
+#endif
 static int	select_div_scale(const NumericVar *var1, const NumericVar *var2);
 static void mod_var(const NumericVar *var1, const NumericVar *var2,
 					NumericVar *result);
@@ -8484,7 +8488,32 @@ div_var(const NumericVar *var1, const NumericVar *var2, NumericVar *result,
 	/*
 	 * If the divisor has just one or two digits, delegate to div_var_int(),
 	 * which uses fast short division.
+	 *
+	 * On platforms with 128-bit integer support, and if the divisor has
+	 * three or four digits, delegate to div_var_int64(),
+	 * which also uses fast short division.
 	 */
+	#ifdef HAVE_INT128
+	if (var2ndigits <= 4)
+	{
+		int64		idivisor;
+		int			idivisor_weight;
+
+		idivisor = var2->digits[0];
+		idivisor_weight = var2->weight;
+		for (i = 1; i < var2ndigits; i++)
+		{
+			idivisor *= NBASE;
+			idivisor += var2->digits[i];
+			idivisor_weight--;
+		}
+		if (var2->sign == NUMERIC_NEG)
+			idivisor = -idivisor;
+
+		div_var_int64(var1, idivisor, idivisor_weight, result, rscale, round);
+		return;
+	}
+	#else
 	if (var2ndigits <= 2)
 	{
 		int			idivisor;
@@ -8503,6 +8532,7 @@ div_var(const NumericVar *var1, const NumericVar *var2, NumericVar *result,
 		div_var_int(var1, idivisor, idivisor_weight, result, rscale, round);
 		return;
 	}
+	#endif
 
 	/*
 	 * Otherwise, perform full long division.
@@ -8774,7 +8804,32 @@ div_var_fast(const NumericVar *var1, const NumericVar *var2,
 	/*
 	 * If the divisor has just one or two digits, delegate to div_var_int(),
 	 * which uses fast short division.
+	 *
+	 * On platforms with 128-bit integer support, and if the divisor has
+	 * three or four digits, delegate to div_var_int64(),
+	 * which also uses fast short division.
 	 */
+	#ifdef HAVE_INT128
+	if (var2ndigits <= 4)
+	{
+		int64		idivisor;
+		int			idivisor_weight;
+
+		idivisor = var2->digits[0];
+		idivisor_weight = var2->weight;
+		for (i = 1; i < var2ndigits; i++)
+		{
+			idivisor *= NBASE;
+			idivisor += var2->digits[i];
+			idivisor_weight--;
+		}
+		if (var2->sign == NUMERIC_NEG)
+			idivisor = -idivisor;
+
+		div_var_int64(var1, idivisor, idivisor_weight, result, rscale, round);
+		return;
+	}
+	#else
 	if (var2ndigits <= 2)
 	{
 		int			idivisor;
@@ -8793,6 +8848,7 @@ div_var_fast(const NumericVar *var1, const NumericVar *var2,
 		div_var_int(var1, idivisor, idivisor_weight, result, rscale, round);
 		return;
 	}
+	#endif
 
 	/*
 	 * Otherwise, perform full long division.
@@ -9182,6 +9238,118 @@ div_var_int(const NumericVar *var, int ival, int ival_weight,
 }
 
 
+/*
+ * div_var_int64() -
+ *
+ *	Divide a numeric variable by a 64-bit integer with the specified weight.
+ *	The quotient var / (ival * NBASE^ival_weight) is stored in result.
+ */
+static void
+div_var_int64(const NumericVar *var, int64 ival, int ival_weight,
+			NumericVar *result, int rscale, bool round)
+{
+	NumericDigit *var_digits = var->digits;
+	int			var_ndigits = var->ndigits;
+	int			res_sign;
+	int			res_weight;
+	int			res_ndigits;
+	NumericDigit *res_buf;
+	NumericDigit *res_digits;
+	uint64		divisor;
+	int			i;
+
+	/* Guard against division by zero */
+	if (ival == 0)
+		ereport(ERROR,
+				errcode(ERRCODE_DIVISION_BY_ZERO),
+				errmsg("division by zero"));
+
+	/* Result zero check */
+	if (var_ndigits == 0)
+	{
+		zero_var(result);
+		result->dscale = rscale;
+		return;
+	}
+
+	/*
+	 * Determine the result sign, weight and number of digits to calculate.
+	 * The weight figured here is correct if the emitted quotient has no
+	 * leading zero digits; otherwise strip_var() will fix things up.
+	 */
+	if (var->sign == NUMERIC_POS)
+		res_sign = ival > 0 ? NUMERIC_POS : NUMERIC_NEG;
+	else
+		res_sign = ival > 0 ? NUMERIC_NEG : NUMERIC_POS;
+	res_weight = var->weight - ival_weight;
+	/* The number of accurate result digits we need to produce: */
+	res_ndigits = res_weight + 1 + (rscale + DEC_DIGITS - 1) / DEC_DIGITS;
+	/* ... but always at least 1 */
+	res_ndigits = Max(res_ndigits, 1);
+	/* If rounding needed, figure one more digit to ensure correct result */
+	if (round)
+		res_ndigits++;
+
+	res_buf = digitbuf_alloc(res_ndigits + 1);
+	res_buf[0] = 0;				/* spare digit for later rounding */
+	res_digits = res_buf + 1;
+
+	/*
+	 * Now compute the quotient digits.  This is the short division algorithm
+	 * described in Knuth volume 2, section 4.3.1 exercise 16, except that we
+	 * allow the divisor to exceed the internal base.
+	 *
+	 * In this algorithm, the carry from one digit to the next is at most
+	 * divisor - 1.  Therefore, while processing the next digit, carry may
+	 * become as large as divisor * NBASE - 1, and so it requires a 128-bit
+	 * integer if this exceeds ULONG_MAX.
+	 */
+	divisor = i64abs(ival);
+
+	if (divisor <= ULONG_MAX / NBASE)
+	{
+		/* carry cannot overflow 64 bits */
+		uint64		carry = 0;
+
+		for (i = 0; i < res_ndigits; i++)
+		{
+			carry = carry * NBASE + (i < var_ndigits ? var_digits[i] : 0);
+			res_digits[i] = (NumericDigit) (carry / divisor);
+			carry = carry % divisor;
+		}
+	}
+	else
+	{
+		/* carry may exceed 64 bits */
+		uint128		carry = 0;
+
+		for (i = 0; i < res_ndigits; i++)
+		{
+			carry = carry * NBASE + (i < var_ndigits ? var_digits[i] : 0);
+			res_digits[i] = (NumericDigit) (carry / divisor);
+			carry = carry % divisor;
+		}
+	}
+
+	/* Store the quotient in result */
+	digitbuf_free(result->buf);
+	result->ndigits = res_ndigits;
+	result->buf = res_buf;
+	result->digits = res_digits;
+	result->weight = res_weight;
+	result->sign = res_sign;
+
+	/* Round or truncate to target rscale (and set result->dscale) */
+	if (round)
+		round_var(result, rscale);
+	else
+		trunc_var(result, rscale);
+
+	/* Strip leading/trailing zeroes */
+	strip_var(result);
+}
+
+
 /*
  * Default scale selection for division
  *
#2Dean Rasheed
dean.a.rasheed@gmail.com
In reply to: Joel Jacobson (#1)
Re: [PATCH] Use 128-bit math to accelerate numeric division, when 8 < divisor digits <= 16

On Sun, 22 Jan 2023 at 13:42, Joel Jacobson <joel@compiler.org> wrote:

Hi,

On platforms where we support 128bit integers, we could accelerate division
when the number of digits in the divisor is larger than 8 and less than or
equal to 16 digits, i.e. when the divisor that fits in a 64-bit integer but would
not fit in a 32-bit integer.

Seems like a reasonable idea, with some pretty decent gains.

Note, however, that for a divisor having fewer than 5 or 6 digits,
it's now significantly slower because it's forced to go through
div_var_int64() instead of div_var_int() for all small divisors. So
the var2ndigits <= 2 case needs to come first.

The implementation of div_var_int64() should be in an #ifdef HAVE_INT128 block.

In div_var_int64(), s/ULONG_MAX/PG_UINT64_MAX/

Regards,
Dean

#3Joel Jacobson
joel@compiler.org
In reply to: Dean Rasheed (#2)
Re: [PATCH] Use 128-bit math to accelerate numeric division, when 8 < divisor digits <= 16

On Sun, Jan 22, 2023, at 11:06, Dean Rasheed wrote:

Seems like a reasonable idea, with some pretty decent gains.

Note, however, that for a divisor having fewer than 5 or 6 digits,
it's now significantly slower because it's forced to go through
div_var_int64() instead of div_var_int() for all small divisors. So
the var2ndigits <= 2 case needs to come first.

Can you give a measurable example of when the patch
the way it's written is significantly slower for a divisor having
fewer than 5 or 6 digits, on some platform?

I can't detect any difference at all at my MacBook Pro M1 Max for this example:
EXPLAIN ANALYZE SELECT count(numeric_div_volatile(1,3333)) FROM generate_series(1,1e8);

I did write the code like you suggest first, but changed it,
since I realised the extra "else if" needed could be eliminated,
and thought div_var_int64() wouldn't be slower than div_var_int() since
I thought 64-bit instructions in general are as fast as 32-bit instructions,
on 64-bit platforms.

I'm not suggesting your claim is incorrect, I'm just trying to understand
and verify it experimentally.

The implementation of div_var_int64() should be in an #ifdef HAVE_INT128 block.

In div_var_int64(), s/ULONG_MAX/PG_UINT64_MAX/

OK, thanks, I'll fix, but I'll await your feedback first on the above.

/Joel

#4Dean Rasheed
dean.a.rasheed@gmail.com
In reply to: Joel Jacobson (#3)
Re: [PATCH] Use 128-bit math to accelerate numeric division, when 8 < divisor digits <= 16

On Sun, 22 Jan 2023 at 15:41, Joel Jacobson <joel@compiler.org> wrote:

On Sun, Jan 22, 2023, at 11:06, Dean Rasheed wrote:

Seems like a reasonable idea, with some pretty decent gains.

Note, however, that for a divisor having fewer than 5 or 6 digits,
it's now significantly slower because it's forced to go through
div_var_int64() instead of div_var_int() for all small divisors. So
the var2ndigits <= 2 case needs to come first.

Can you give a measurable example of when the patch
the way it's written is significantly slower for a divisor having
fewer than 5 or 6 digits, on some platform?

I just modified the previous test you posted:

\timing on
SELECT count(numeric_div_volatile(1e131071,123456)) FROM generate_series(1,1e4);

Time: 2048.060 ms (00:02.048) -- HEAD
Time: 2422.720 ms (00:02.423) -- With patch

I did write the code like you suggest first, but changed it,
since I realised the extra "else if" needed could be eliminated,
and thought div_var_int64() wouldn't be slower than div_var_int() since
I thought 64-bit instructions in general are as fast as 32-bit instructions,
on 64-bit platforms.

Apparently it can make a difference. Probably something to do with
having less data to move around. I remember noticing that when I wrote
div_var_int(), which is why I split it into 2 branches in that way.

Regards,
Dean

#5Joel Jacobson
joel@compiler.org
In reply to: Dean Rasheed (#4)
1 attachment(s)
Re: [PATCH] Use 128-bit math to accelerate numeric division, when 8 < divisor digits <= 16

On Sun, Jan 22, 2023, at 14:25, Dean Rasheed wrote:

I just modified the previous test you posted:

\timing on
SELECT count(numeric_div_volatile(1e131071,123456)) FROM generate_series(1,1e4);

Time: 2048.060 ms (00:02.048) -- HEAD
Time: 2422.720 ms (00:02.423) -- With patch

...

Apparently it can make a difference. Probably something to do with
having less data to move around. I remember noticing that when I wrote
div_var_int(), which is why I split it into 2 branches in that way.

Many thanks for feedback. Nice catch! New patch attached.

Interesting, I'm not able to reproduce this on my MacBook Pro M1 Max:

SELECT version;
PostgreSQL 16devel on aarch64-apple-darwin22.2.0, compiled by Apple clang version 14.0.0 (clang-1400.0.29.202), 64-bit

SELECT count(numeric_div_volatile(1e131071,123456)) FROM generate_series(1,1e 4);
Time: 1569.730 ms (00:01.570) - HEAD
Time: 1569.918 ms (00:01.570) -- div_var_int64.patch
Time: 1569.038 ms (00:01.569) -- div_var_int64-2.patch

Just curious, what platform are you on?

/Joel

Attachments:

div_var_int64-2.patchapplication/octet-stream; name=div_var_int64-2.patchDownload
From 30d718db26f442f558e2df9a7604b8bbdcd4ae94 Mon Sep 17 00:00:00 2001
From: Joel Jakobsson <joel@compiler.org>
Date: Sun, 22 Jan 2023 12:57:30 -0400
Subject: [PATCH 1/5] Use 128-bit math to accelerate numeric division, when 8 <
 divisor digits <= 16

This patch adds div_var_int64(), which is similar to the existing div_var_int(),
but accepts a 64-bit divisor instead of a 32-bit divisor.

The new function is used within div_var() and div_var_fast().
---
 src/backend/utils/adt/numeric.c | 167 ++++++++++++++++++++++++++++++++
 1 file changed, 167 insertions(+)

diff --git a/src/backend/utils/adt/numeric.c b/src/backend/utils/adt/numeric.c
index a6409ecbee..e48493ac4a 100644
--- a/src/backend/utils/adt/numeric.c
+++ b/src/backend/utils/adt/numeric.c
@@ -554,6 +554,10 @@ static void div_var_fast(const NumericVar *var1, const NumericVar *var2,
 						 NumericVar *result, int rscale, bool round);
 static void div_var_int(const NumericVar *var, int ival, int ival_weight,
 						NumericVar *result, int rscale, bool round);
+#ifdef HAVE_INT128
+static void div_var_int64(const NumericVar *var, int64 ival, int ival_weight,
+						NumericVar *result, int rscale, bool round);
+#endif
 static int	select_div_scale(const NumericVar *var1, const NumericVar *var2);
 static void mod_var(const NumericVar *var1, const NumericVar *var2,
 					NumericVar *result);
@@ -8484,6 +8488,10 @@ div_var(const NumericVar *var1, const NumericVar *var2, NumericVar *result,
 	/*
 	 * If the divisor has just one or two digits, delegate to div_var_int(),
 	 * which uses fast short division.
+	 *
+	 * On platforms with 128-bit integer support, and if the divisor has
+	 * three or four digits, delegate to div_var_int64(),
+	 * which also uses fast short division.
 	 */
 	if (var2ndigits <= 2)
 	{
@@ -8503,6 +8511,27 @@ div_var(const NumericVar *var1, const NumericVar *var2, NumericVar *result,
 		div_var_int(var1, idivisor, idivisor_weight, result, rscale, round);
 		return;
 	}
+	#ifdef HAVE_INT128
+	else if (var2ndigits <= 4)
+	{
+		int64		idivisor;
+		int			idivisor_weight;
+
+		idivisor = var2->digits[0];
+		idivisor_weight = var2->weight;
+		for (i = 1; i < var2ndigits; i++)
+		{
+			idivisor *= NBASE;
+			idivisor += var2->digits[i];
+			idivisor_weight--;
+		}
+		if (var2->sign == NUMERIC_NEG)
+			idivisor = -idivisor;
+
+		div_var_int64(var1, idivisor, idivisor_weight, result, rscale, round);
+		return;
+	}
+	#endif
 
 	/*
 	 * Otherwise, perform full long division.
@@ -8774,6 +8803,10 @@ div_var_fast(const NumericVar *var1, const NumericVar *var2,
 	/*
 	 * If the divisor has just one or two digits, delegate to div_var_int(),
 	 * which uses fast short division.
+	 *
+	 * On platforms with 128-bit integer support, and if the divisor has
+	 * three or four digits, delegate to div_var_int64(),
+	 * which also uses fast short division.
 	 */
 	if (var2ndigits <= 2)
 	{
@@ -8793,6 +8826,27 @@ div_var_fast(const NumericVar *var1, const NumericVar *var2,
 		div_var_int(var1, idivisor, idivisor_weight, result, rscale, round);
 		return;
 	}
+	#ifdef HAVE_INT128
+	else if (var2ndigits <= 4)
+	{
+		int64		idivisor;
+		int			idivisor_weight;
+
+		idivisor = var2->digits[0];
+		idivisor_weight = var2->weight;
+		for (i = 1; i < var2ndigits; i++)
+		{
+			idivisor *= NBASE;
+			idivisor += var2->digits[i];
+			idivisor_weight--;
+		}
+		if (var2->sign == NUMERIC_NEG)
+			idivisor = -idivisor;
+
+		div_var_int64(var1, idivisor, idivisor_weight, result, rscale, round);
+		return;
+	}
+	#endif
 
 	/*
 	 * Otherwise, perform full long division.
@@ -9182,6 +9236,119 @@ div_var_int(const NumericVar *var, int ival, int ival_weight,
 }
 
 
+#ifdef HAVE_INT128
+/*
+ * div_var_int64() -
+ *
+ *	Divide a numeric variable by a 64-bit integer with the specified weight.
+ *	The quotient var / (ival * NBASE^ival_weight) is stored in result.
+ */
+static void
+div_var_int64(const NumericVar *var, int64 ival, int ival_weight,
+			NumericVar *result, int rscale, bool round)
+{
+	NumericDigit *var_digits = var->digits;
+	int			var_ndigits = var->ndigits;
+	int			res_sign;
+	int			res_weight;
+	int			res_ndigits;
+	NumericDigit *res_buf;
+	NumericDigit *res_digits;
+	uint64		divisor;
+	int			i;
+
+	/* Guard against division by zero */
+	if (ival == 0)
+		ereport(ERROR,
+				errcode(ERRCODE_DIVISION_BY_ZERO),
+				errmsg("division by zero"));
+
+	/* Result zero check */
+	if (var_ndigits == 0)
+	{
+		zero_var(result);
+		result->dscale = rscale;
+		return;
+	}
+
+	/*
+	 * Determine the result sign, weight and number of digits to calculate.
+	 * The weight figured here is correct if the emitted quotient has no
+	 * leading zero digits; otherwise strip_var() will fix things up.
+	 */
+	if (var->sign == NUMERIC_POS)
+		res_sign = ival > 0 ? NUMERIC_POS : NUMERIC_NEG;
+	else
+		res_sign = ival > 0 ? NUMERIC_NEG : NUMERIC_POS;
+	res_weight = var->weight - ival_weight;
+	/* The number of accurate result digits we need to produce: */
+	res_ndigits = res_weight + 1 + (rscale + DEC_DIGITS - 1) / DEC_DIGITS;
+	/* ... but always at least 1 */
+	res_ndigits = Max(res_ndigits, 1);
+	/* If rounding needed, figure one more digit to ensure correct result */
+	if (round)
+		res_ndigits++;
+
+	res_buf = digitbuf_alloc(res_ndigits + 1);
+	res_buf[0] = 0;				/* spare digit for later rounding */
+	res_digits = res_buf + 1;
+
+	/*
+	 * Now compute the quotient digits.  This is the short division algorithm
+	 * described in Knuth volume 2, section 4.3.1 exercise 16, except that we
+	 * allow the divisor to exceed the internal base.
+	 *
+	 * In this algorithm, the carry from one digit to the next is at most
+	 * divisor - 1.  Therefore, while processing the next digit, carry may
+	 * become as large as divisor * NBASE - 1, and so it requires a 128-bit
+	 * integer if this exceeds PG_UINT64_MAX.
+	 */
+	divisor = i64abs(ival);
+
+	if (divisor <= PG_UINT64_MAX / NBASE)
+	{
+		/* carry cannot overflow 64 bits */
+		uint64		carry = 0;
+
+		for (i = 0; i < res_ndigits; i++)
+		{
+			carry = carry * NBASE + (i < var_ndigits ? var_digits[i] : 0);
+			res_digits[i] = (NumericDigit) (carry / divisor);
+			carry = carry % divisor;
+		}
+	}
+	else
+	{
+		/* carry may exceed 64 bits */
+		uint128		carry = 0;
+
+		for (i = 0; i < res_ndigits; i++)
+		{
+			carry = carry * NBASE + (i < var_ndigits ? var_digits[i] : 0);
+			res_digits[i] = (NumericDigit) (carry / divisor);
+			carry = carry % divisor;
+		}
+	}
+
+	/* Store the quotient in result */
+	digitbuf_free(result->buf);
+	result->ndigits = res_ndigits;
+	result->buf = res_buf;
+	result->digits = res_digits;
+	result->weight = res_weight;
+	result->sign = res_sign;
+
+	/* Round or truncate to target rscale (and set result->dscale) */
+	if (round)
+		round_var(result, rscale);
+	else
+		trunc_var(result, rscale);
+
+	/* Strip leading/trailing zeroes */
+	strip_var(result);
+}
+#endif
+
 /*
  * Default scale selection for division
  *
-- 
2.37.1 (Apple Git-137.1)

#6John Naylor
john.naylor@enterprisedb.com
In reply to: Joel Jacobson (#3)
Re: [PATCH] Use 128-bit math to accelerate numeric division, when 8 < divisor digits <= 16

On Sun, Jan 22, 2023 at 10:42 PM Joel Jacobson <joel@compiler.org> wrote:

I did write the code like you suggest first, but changed it,
since I realised the extra "else if" needed could be eliminated,
and thought div_var_int64() wouldn't be slower than div_var_int() since
I thought 64-bit instructions in general are as fast as 32-bit

instructions,

on 64-bit platforms.

According to Agner's instruction tables [1]https://www.agner.org/optimize/instruction_tables.pdf, integer division on Skylake
(for example) has a latency of 26 cycles for 32-bit operands, and 42-95
cycles for 64-bit.

[1]: https://www.agner.org/optimize/instruction_tables.pdf

--
John Naylor
EDB: http://www.enterprisedb.com

#7Dean Rasheed
dean.a.rasheed@gmail.com
In reply to: John Naylor (#6)
Re: [PATCH] Use 128-bit math to accelerate numeric division, when 8 < divisor digits <= 16

On Mon, 23 Jan 2023 at 05:06, John Naylor <john.naylor@enterprisedb.com> wrote:

According to Agner's instruction tables [1], integer division on Skylake (for example) has a latency of 26 cycles for 32-bit operands, and 42-95 cycles for 64-bit.

[1] https://www.agner.org/optimize/instruction_tables.pdf

Thanks, that's a very useful reference.

(And I do indeed have one of those CPUs, which explains what I was seeing.)

Regards,
Dean

#8Dean Rasheed
dean.a.rasheed@gmail.com
In reply to: Joel Jacobson (#5)
Re: [PATCH] Use 128-bit math to accelerate numeric division, when 8 < divisor digits <= 16

On Sun, 22 Jan 2023 at 22:49, Joel Jacobson <joel@compiler.org> wrote:

Many thanks for feedback. Nice catch! New patch attached.

Cool, that resolves the performance issues I was seeing for smaller
divisors (which also had a noticeable impact on the numeric_big
regression test).

After some more testing, the gains look good to me, and I wasn't able
to find any cases where it made things slower, so I've gone ahead and
pushed it.

Regards,
Dean