gx

chenyc

2025-06-12 7b72ac13a83764a662159d4a49b7fffb90476ecb

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/**
 * @license
 * Copyright 2020 Google LLC. All Rights Reserved.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 * =============================================================================
 */
import { backend_util, Dilation2DBackpropInput, util } from '@tensorflow/tfjs-core';
export const dilation2DBackpropInputConfig = {
    kernelName: Dilation2DBackpropInput,
    backendName: 'cpu',
    kernelFunc: ({ inputs, backend, attrs }) => {
        const { x, filter, dy } = inputs;
        const { strides, pad, dilations } = attrs;
        const cpuBackend = backend;
        const $x = util.toNestedArray(x.shape, cpuBackend.data.get(x.dataId).values);
        const $filter = util.toNestedArray(filter.shape, cpuBackend.data.get(filter.dataId).values);
        const { batchSize, inHeight, inWidth, inChannels, outHeight, outWidth, padInfo, strideHeight, strideWidth, filterHeight, filterWidth, dilationHeight, dilationWidth, outShape } = backend_util.computeDilation2DInfo(x.shape, filter.shape, strides, pad, 'NHWC' /* dataFormat */, dilations);
        util.assert(dy.rank === outShape.length, () => `Error in ${Dilation2DBackpropInput}, dy ` +
            `must have the same rank as output ${outShape.length}, but got ` +
            `${dy.rank}`);
        const $dy = util.toNestedArray(outShape, cpuBackend.data.get(dy.dataId).values);
        // The computed gradients has the same dimensions as the input:
        // [batch, inputHeight, inputCols, inChannel]
        const gradients = util.makeZerosNestedTypedArray(x.shape, x.dtype);
        // In the case of multiple argmax branches, we only back-propagate along the
        // last branch, i.e., the one with largest value of `h * filter_cols + w`,
        // similarly to the max-pooling backward routines.
        // This implementation follows the TF c++ implementation:
        // https://github.com/tensorflow/tensorflow/blob/d9a3a849edc198e90172bc58eb293de457f9d986/tensorflow/core/kernels/dilation_ops.cc
        for (let b = 0; b < batchSize; ++b) {
            for (let hOut = 0; hOut < outHeight; ++hOut) {
                const hBeg = hOut * strideHeight - padInfo.top;
                for (let wOut = 0; wOut < outWidth; ++wOut) {
                    const wBeg = wOut * strideWidth - padInfo.left;
                    for (let d = 0; d < inChannels; ++d) {
                        let curVal = Number.MIN_SAFE_INTEGER;
                        let hInMax = (hBeg < 0) ? 0 : hBeg;
                        let wInMax = (wBeg < 0) ? 0 : wBeg;
                        for (let h = 0; h < filterHeight; ++h) {
                            const hIn = hBeg + h * dilationHeight;
                            if (hIn >= 0 && hIn < inHeight) {
                                for (let w = 0; w < filterWidth; ++w) {
                                    const wIn = wBeg + w * dilationWidth;
                                    if (wIn >= 0 && wIn < inWidth) {
                                        const val = $x[b][hIn][wIn][d] + $filter[h][w][d];
                                        if (val > curVal) {
                                            curVal = val;
                                            hInMax = hIn;
                                            wInMax = wIn;
                                        }
                                    }
                                }
                            }
                        }
                        gradients[b][hInMax][wInMax][d] += $dy[b][hOut][wOut][d];
                    }
                }
            }
        }
        const dataId = cpuBackend.write(util.toTypedArray(gradients, x.dtype), x.shape, x.dtype);
        return { dataId, shape: x.shape, dtype: x.dtype };
    }
};
//# sourceMappingURL=data:application/json;base64,eyJ2ZXJzaW9uIjozLCJmaWxlIjoiRGlsYXRpb24yREJhY2twcm9wSW5wdXQuanMiLCJzb3VyY2VSb290IjoiIiwic291cmNlcyI6WyIuLi8uLi8uLi8uLi8uLi8uLi90ZmpzLWJhY2tlbmQtY3B1L3NyYy9rZXJuZWxzL0RpbGF0aW9uMkRCYWNrcHJvcElucHV0LnRzIl0sIm5hbWVzIjpbXSwibWFwcGluZ3MiOiJBQUFBOzs7Ozs7Ozs7Ozs7Ozs7R0FlRztBQUVILE9BQU8sRUFBQyxZQUFZLEVBQW1CLHVCQUF1QixFQUFrQyxJQUFJLEVBQUMsTUFBTSx1QkFBdUIsQ0FBQztBQUtuSSxNQUFNLENBQUMsTUFBTSw2QkFBNkIsR0FBaUI7SUFDekQsVUFBVSxFQUFFLHVCQUF1QjtJQUNuQyxXQUFXLEVBQUUsS0FBSztJQUNsQixVQUFVLEVBQUUsQ0FBQyxFQUFDLE1BQU0sRUFBRSxPQUFPLEVBQUUsS0FBSyxFQUFDLEVBQUUsRUFBRTtRQUN2QyxNQUFNLEVBQUMsQ0FBQyxFQUFFLE1BQU0sRUFBRSxFQUFFLEVBQUMsR0FDakIsTUFBdUQsQ0FBQztRQUM1RCxNQUFNLEVBQUMsT0FBTyxFQUFFLEdBQUcsRUFBRSxTQUFTLEVBQUMsR0FBRyxLQUFtQyxDQUFDO1FBQ3RFLE1BQU0sVUFBVSxHQUFHLE9BQXlCLENBQUM7UUFFN0MsTUFBTSxFQUFFLEdBQ0osSUFBSSxDQUFDLGFBQWEsQ0FDZCxDQUFDLENBQUMsS0FBSyxFQUFFLFVBQVUsQ0FBQyxJQUFJLENBQUMsR0FBRyxDQUFDLENBQUMsQ0FBQyxNQUFNLENBQUMsQ0FBQyxNQUFvQixDQUNqRCxDQUFDO1FBRW5CLE1BQU0sT0FBTyxHQUFHLElBQUksQ0FBQyxhQUFhLENBQ2QsTUFBTSxDQUFDLEtBQUssRUFDWixVQUFVLENBQUMsSUFBSSxDQUFDLEdBQUcsQ0FBQyxNQUFNLENBQUMsTUFBTSxDQUFDLENBQUMsTUFDckIsQ0FBaUIsQ0FBQztRQUVwRCxNQUFNLEVBQ0osU0FBUyxFQUNULFFBQVEsRUFDUixPQUFPLEVBQ1AsVUFBVSxFQUNWLFNBQVMsRUFDVCxRQUFRLEVBQ1IsT0FBTyxFQUNQLFlBQVksRUFDWixXQUFXLEVBQ1gsWUFBWSxFQUNaLFdBQVcsRUFDWCxjQUFjLEVBQ2QsYUFBYSxFQUNiLFFBQVEsRUFDVCxHQUNHLFlBQVksQ0FBQyxxQkFBcUIsQ0FDOUIsQ0FBQyxDQUFDLEtBQXlDLEVBQzNDLE1BQU0sQ0FBQyxLQUFpQyxFQUFFLE9BQU8sRUFBRSxHQUFHLEVBQ3RELE1BQU0sQ0FBQyxnQkFBZ0IsRUFBRSxTQUFTLENBQUMsQ0FBQztRQUU1QyxJQUFJLENBQUMsTUFBTSxDQUNQLEVBQUUsQ0FBQyxJQUFJLEtBQUssUUFBUSxDQUFDLE1BQU0sRUFDM0IsR0FBRyxFQUFFLENBQUMsWUFBWSx1QkFBdUIsT0FBTztZQUM1QyxxQ0FBcUMsUUFBUSxDQUFDLE1BQU0sWUFBWTtZQUNoRSxHQUFHLEVBQUUsQ0FBQyxJQUFJLEVBQUUsQ0FBQyxDQUFDO1FBRXRCLE1BQU0sR0FBRyxHQUNMLElBQUksQ0FBQyxhQUFhLENBQ2QsUUFBUSxFQUFFLFVBQVUsQ0FBQyxJQUFJLENBQUMsR0FBRyxDQUFDLEVBQUUsQ0FBQyxNQUFNLENBQUMsQ0FBQyxNQUFvQixDQUNuRCxDQUFDO1FBRW5CLCtEQUErRDtRQUMvRCw2Q0FBNkM7UUFDN0MsTUFBTSxTQUFTLEdBQ1gsSUFBSSxDQUFDLHlCQUF5QixDQUFDLENBQUMsQ0FBQyxLQUFLLEVBQUUsQ0FBQyxDQUFDLEtBQUssQ0FBbUIsQ0FBQztRQUV2RSw0RUFBNEU7UUFDNUUsMEVBQTBFO1FBQzFFLGtEQUFrRDtRQUNsRCx5REFBeUQ7UUFDekQsaUlBQWlJO1FBQ2pJLEtBQUssSUFBSSxDQUFDLEdBQUcsQ0FBQyxFQUFFLENBQUMsR0FBRyxTQUFTLEVBQUUsRUFBRSxDQUFDLEVBQUU7WUFDbEMsS0FBSyxJQUFJLElBQUksR0FBRyxDQUFDLEVBQUUsSUFBSSxHQUFHLFNBQVMsRUFBRSxFQUFFLElBQUksRUFBRTtnQkFDM0MsTUFBTSxJQUFJLEdBQUcsSUFBSSxHQUFHLFlBQVksR0FBRyxPQUFPLENBQUMsR0FBRyxDQUFDO2dCQUMvQyxLQUFLLElBQUksSUFBSSxHQUFHLENBQUMsRUFBRSxJQUFJLEdBQUcsUUFBUSxFQUFFLEVBQUUsSUFBSSxFQUFFO29CQUMxQyxNQUFNLElBQUksR0FBRyxJQUFJLEdBQUcsV0FBVyxHQUFHLE9BQU8sQ0FBQyxJQUFJLENBQUM7b0JBQy9DLEtBQUssSUFBSSxDQUFDLEdBQUcsQ0FBQyxFQUFFLENBQUMsR0FBRyxVQUFVLEVBQUUsRUFBRSxDQUFDLEVBQUU7d0JBQ25DLElBQUksTUFBTSxHQUFHLE1BQU0sQ0FBQyxnQkFBZ0IsQ0FBQzt3QkFDckMsSUFBSSxNQUFNLEdBQUcsQ0FBQyxJQUFJLEdBQUcsQ0FBQyxDQUFDLENBQUMsQ0FBQyxDQUFDLENBQUMsQ0FBQyxDQUFDLENBQUMsSUFBSSxDQUFDO3dCQUNuQyxJQUFJLE1BQU0sR0FBRyxDQUFDLElBQUksR0FBRyxDQUFDLENBQUMsQ0FBQyxDQUFDLENBQUMsQ0FBQyxDQUFDLENBQUMsQ0FBQyxJQUFJLENBQUM7d0JBQ25DLEtBQUssSUFBSSxDQUFDLEdBQUcsQ0FBQyxFQUFFLENBQUMsR0FBRyxZQUFZLEVBQUUsRUFBRSxDQUFDLEVBQUU7NEJBQ3JDLE1BQU0sR0FBRyxHQUFHLElBQUksR0FBRyxDQUFDLEdBQUcsY0FBYyxDQUFDOzRCQUN0QyxJQUFJLEdBQUcsSUFBSSxDQUFDLElBQUksR0FBRyxHQUFHLFFBQVEsRUFBRTtnQ0FDOUIsS0FBSyxJQUFJLENBQUMsR0FBRyxDQUFDLEVBQUUsQ0FBQyxHQUFHLFdBQVcsRUFBRSxFQUFFLENBQUMsRUFBRTtvQ0FDcEMsTUFBTSxHQUFHLEdBQUcsSUFBSSxHQUFHLENBQUMsR0FBRyxhQUFhLENBQUM7b0NBQ3JDLElBQUksR0FBRyxJQUFJLENBQUMsSUFBSSxHQUFHLEdBQUcsT0FBTyxFQUFFO3dDQUM3QixNQUFNLEdBQUcsR0FBRyxFQUFFLENBQUMsQ0FBQyxDQUFDLENBQUMsR0FBRyxDQUFDLENBQUMsR0FBRyxDQUFDLENBQUMsQ0FBQyxDQUFDLEdBQUcsT0FBTyxDQUFDLENBQUMsQ0FBQyxDQUFDLENBQUMsQ0FBQyxDQUFDLENBQUMsQ0FBQyxDQUFDO3dDQUNsRCxJQUFJLEdBQUcsR0FBRyxNQUFNLEVBQUU7NENBQ2hCLE1BQU0sR0FBRyxHQUFHLENBQUM7NENBQ2IsTUFBTSxHQUFHLEdBQUcsQ0FBQzs0Q0FDYixNQUFNLEdBQUcsR0FBRyxDQUFDO3lDQUNkO3FDQUNGO2lDQUNGOzZCQUNGO3lCQUNGO3dCQUNELFNBQVMsQ0FBQyxDQUFDLENBQUMsQ0FBQyxNQUFNLENBQUMsQ0FBQyxNQUFNLENBQUMsQ0FBQyxDQUFDLENBQUMsSUFBSSxHQUFHLENBQUMsQ0FBQyxDQUFDLENBQUMsSUFBSSxDQUFDLENBQUMsSUFBSSxDQUFDLENBQUMsQ0FBQyxDQUFDLENBQUM7cUJBQzFEO2lCQUNGO2FBQ0Y7U0FDRjtRQUVELE1BQU0sTUFBTSxHQUFHLFVBQVUsQ0FBQyxLQUFLLENBQzNCLElBQUksQ0FBQyxZQUFZLENBQUMsU0FBUyxFQUFFLENBQUMsQ0FBQyxLQUFLLENBQUMsRUFBRSxDQUFDLENBQUMsS0FBSyxFQUFFLENBQUMsQ0FBQyxLQUFLLENBQUMsQ0FBQztRQUU3RCxPQUFPLEVBQUMsTUFBTSxFQUFFLEtBQUssRUFBRSxDQUFDLENBQUMsS0FBSyxFQUFFLEtBQUssRUFBRSxDQUFDLENBQUMsS0FBSyxFQUFDLENBQUM7SUFDbEQsQ0FBQztDQUNGLENBQUMiLCJzb3VyY2VzQ29udGVudCI6WyIvKipcbiAqIEBsaWNlbnNlXG4gKiBDb3B5cmlnaHQgMjAyMCBHb29nbGUgTExDLiBBbGwgUmlnaHRzIFJlc2VydmVkLlxuICogTGljZW5zZWQgdW5kZXIgdGhlIEFwYWNoZSBMaWNlbnNlLCBWZXJzaW9uIDIuMCAodGhlIFwiTGljZW5zZVwiKTtcbiAqIHlvdSBtYXkgbm90IHVzZSB0aGlzIGZpbGUgZXhjZXB0IGluIGNvbXBsaWFuY2Ugd2l0aCB0aGUgTGljZW5zZS5cbiAqIFlvdSBtYXkgb2J0YWluIGEgY29weSBvZiB0aGUgTGljZW5zZSBhdFxuICpcbiAqIGh0dHA6Ly93d3cuYXBhY2hlLm9yZy9saWNlbnNlcy9MSUNFTlNFLTIuMFxuICpcbiAqIFVubGVzcyByZXF1aXJlZCBieSBhcHBsaWNhYmxlIGxhdyBvciBhZ3JlZWQgdG8gaW4gd3JpdGluZywgc29mdHdhcmVcbiAqIGRpc3RyaWJ1dGVkIHVuZGVyIHRoZSBMaWNlbnNlIGlzIGRpc3RyaWJ1dGVkIG9uIGFuIFwiQVMgSVNcIiBCQVNJUyxcbiAqIFdJVEhPVVQgV0FSUkFOVElFUyBPUiBDT05ESVRJT05TIE9GIEFOWSBLSU5ELCBlaXRoZXIgZXhwcmVzcyBvciBpbXBsaWVkLlxuICogU2VlIHRoZSBMaWNlbnNlIGZvciB0aGUgc3BlY2lmaWMgbGFuZ3VhZ2UgZ292ZXJuaW5nIHBlcm1pc3Npb25zIGFuZFxuICogbGltaXRhdGlvbnMgdW5kZXIgdGhlIExpY2Vuc2UuXG4gKiA9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PVxuICovXG5cbmltcG9ydCB7YmFja2VuZF91dGlsLCBEaWxhdGlvbjJEQXR0cnMsIERpbGF0aW9uMkRCYWNrcHJvcElucHV0LCBUZW5zb3IzRCwgVGVuc29yNEQsIFR5cGVkQXJyYXksIHV0aWx9IGZyb20gJ0B0ZW5zb3JmbG93L3RmanMtY29yZSc7XG5pbXBvcnQge0tlcm5lbENvbmZpZ30gZnJvbSAnQHRlbnNvcmZsb3cvdGZqcy1jb3JlJztcblxuaW1wb3J0IHtNYXRoQmFja2VuZENQVX0gZnJvbSAnLi4vYmFja2VuZF9jcHUnO1xuXG5leHBvcnQgY29uc3QgZGlsYXRpb24yREJhY2twcm9wSW5wdXRDb25maWc6IEtlcm5lbENvbmZpZyA9IHtcbiAga2VybmVsTmFtZTogRGlsYXRpb24yREJhY2twcm9wSW5wdXQsXG4gIGJhY2tlbmROYW1lOiAnY3B1JyxcbiAga2VybmVsRnVuYzogKHtpbnB1dHMsIGJhY2tlbmQsIGF0dHJzfSkgPT4ge1xuICAgIGNvbnN0IHt4LCBmaWx0ZXIsIGR5fSA9XG4gICAgICAgIGlucHV0cyBhcyB7eDogVGVuc29yNEQsIGZpbHRlcjogVGVuc29yM0QsIGR5OiBUZW5zb3I0RH07XG4gICAgY29uc3Qge3N0cmlkZXMsIHBhZCwgZGlsYXRpb25zfSA9IGF0dHJzIGFzIHVua25vd24gYXMgRGlsYXRpb24yREF0dHJzO1xuICAgIGNvbnN0IGNwdUJhY2tlbmQgPSBiYWNrZW5kIGFzIE1hdGhCYWNrZW5kQ1BVO1xuXG4gICAgY29uc3QgJHggPVxuICAgICAgICB1dGlsLnRvTmVzdGVkQXJyYXkoXG4gICAgICAgICAgICB4LnNoYXBlLCBjcHVCYWNrZW5kLmRhdGEuZ2V0KHguZGF0YUlkKS52YWx1ZXMgYXMgVHlwZWRBcnJheSkgYXNcbiAgICAgICAgbnVtYmVyW11bXVtdW107XG5cbiAgICBjb25zdCAkZmlsdGVyID0gdXRpbC50b05lc3RlZEFycmF5KFxuICAgICAgICAgICAgICAgICAgICAgICAgZmlsdGVyLnNoYXBlLFxuICAgICAgICAgICAgICAgICAgICAgICAgY3B1QmFja2VuZC5kYXRhLmdldChmaWx0ZXIuZGF0YUlkKS52YWx1ZXMgYXNcbiAgICAgICAgICAgICAgICAgICAgICAgICAgICBUeXBlZEFycmF5KSBhcyBudW1iZXJbXVtdW107XG5cbiAgICBjb25zdCB7XG4gICAgICBiYXRjaFNpemUsXG4gICAgICBpbkhlaWdodCxcbiAgICAgIGluV2lkdGgsXG4gICAgICBpbkNoYW5uZWxzLFxuICAgICAgb3V0SGVpZ2h0LFxuICAgICAgb3V0V2lkdGgsXG4gICAgICBwYWRJbmZvLFxuICAgICAgc3RyaWRlSGVpZ2h0LFxuICAgICAgc3RyaWRlV2lkdGgsXG4gICAgICBmaWx0ZXJIZWlnaHQsXG4gICAgICBmaWx0ZXJXaWR0aCxcbiAgICAgIGRpbGF0aW9uSGVpZ2h0LFxuICAgICAgZGlsYXRpb25XaWR0aCxcbiAgICAgIG91dFNoYXBlXG4gICAgfSA9XG4gICAgICAgIGJhY2tlbmRfdXRpbC5jb21wdXRlRGlsYXRpb24yREluZm8oXG4gICAgICAgICAgICB4LnNoYXBlIGFzIFtudW1iZXIsIG51bWJlciwgbnVtYmVyLCBudW1iZXJdLFxuICAgICAgICAgICAgZmlsdGVyLnNoYXBlIGFzIFtudW1iZXIsIG51bWJlciwgbnVtYmVyXSwgc3RyaWRlcywgcGFkLFxuICAgICAgICAgICAgJ05IV0MnIC8qIGRhdGFGb3JtYXQgKi8sIGRpbGF0aW9ucyk7XG5cbiAgICB1dGlsLmFzc2VydChcbiAgICAgICAgZHkucmFuayA9PT0gb3V0U2hhcGUubGVuZ3RoLFxuICAgICAgICAoKSA9PiBgRXJyb3IgaW4gJHtEaWxhdGlvbjJEQmFja3Byb3BJbnB1dH0sIGR5IGAgK1xuICAgICAgICAgICAgYG11c3QgaGF2ZSB0aGUgc2FtZSByYW5rIGFzIG91dHB1dCAke291dFNoYXBlLmxlbmd0aH0sIGJ1dCBnb3QgYCArXG4gICAgICAgICAgICBgJHtkeS5yYW5rfWApO1xuXG4gICAgY29uc3QgJGR5ID1cbiAgICAgICAgdXRpbC50b05lc3RlZEFycmF5KFxuICAgICAgICAgICAgb3V0U2hhcGUsIGNwdUJhY2tlbmQuZGF0YS5nZXQoZHkuZGF0YUlkKS52YWx1ZXMgYXMgVHlwZWRBcnJheSkgYXNcbiAgICAgICAgbnVtYmVyW11bXVtdW107XG5cbiAgICAvLyBUaGUgY29tcHV0ZWQgZ3JhZGllbnRzIGhhcyB0aGUgc2FtZSBkaW1lbnNpb25zIGFzIHRoZSBpbnB1dDpcbiAgICAvLyBbYmF0Y2gsIGlucHV0SGVpZ2h0LCBpbnB1dENvbHMsIGluQ2hhbm5lbF1cbiAgICBjb25zdCBncmFkaWVudHMgPVxuICAgICAgICB1dGlsLm1ha2VaZXJvc05lc3RlZFR5cGVkQXJyYXkoeC5zaGFwZSwgeC5kdHlwZSkgYXMgbnVtYmVyW11bXVtdW107XG5cbiAgICAvLyBJbiB0aGUgY2FzZSBvZiBtdWx0aXBsZSBhcmdtYXggYnJhbmNoZXMsIHdlIG9ubHkgYmFjay1wcm9wYWdhdGUgYWxvbmcgdGhlXG4gICAgLy8gbGFzdCBicmFuY2gsIGkuZS4sIHRoZSBvbmUgd2l0aCBsYXJnZXN0IHZhbHVlIG9mIGBoICogZmlsdGVyX2NvbHMgKyB3YCxcbiAgICAvLyBzaW1pbGFybHkgdG8gdGhlIG1heC1wb29saW5nIGJhY2t3YXJkIHJvdXRpbmVzLlxuICAgIC8vIFRoaXMgaW1wbGVtZW50YXRpb24gZm9sbG93cyB0aGUgVEYgYysrIGltcGxlbWVudGF0aW9uOlxuICAgIC8vIGh0dHBzOi8vZ2l0aHViLmNvbS90ZW5zb3JmbG93L3RlbnNvcmZsb3cvYmxvYi9kOWEzYTg0OWVkYzE5OGU5MDE3MmJjNThlYjI5M2RlNDU3ZjlkOTg2L3RlbnNvcmZsb3cvY29yZS9rZXJuZWxzL2RpbGF0aW9uX29wcy5jY1xuICAgIGZvciAobGV0IGIgPSAwOyBiIDwgYmF0Y2hTaXplOyArK2IpIHtcbiAgICAgIGZvciAobGV0IGhPdXQgPSAwOyBoT3V0IDwgb3V0SGVpZ2h0OyArK2hPdXQpIHtcbiAgICAgICAgY29uc3QgaEJlZyA9IGhPdXQgKiBzdHJpZGVIZWlnaHQgLSBwYWRJbmZvLnRvcDtcbiAgICAgICAgZm9yIChsZXQgd091dCA9IDA7IHdPdXQgPCBvdXRXaWR0aDsgKyt3T3V0KSB7XG4gICAgICAgICAgY29uc3Qgd0JlZyA9IHdPdXQgKiBzdHJpZGVXaWR0aCAtIHBhZEluZm8ubGVmdDtcbiAgICAgICAgICBmb3IgKGxldCBkID0gMDsgZCA8IGluQ2hhbm5lbHM7ICsrZCkge1xuICAgICAgICAgICAgbGV0IGN1clZhbCA9IE51bWJlci5NSU5fU0FGRV9JTlRFR0VSO1xuICAgICAgICAgICAgbGV0IGhJbk1heCA9IChoQmVnIDwgMCkgPyAwIDogaEJlZztcbiAgICAgICAgICAgIGxldCB3SW5NYXggPSAod0JlZyA8IDApID8gMCA6IHdCZWc7XG4gICAgICAgICAgICBmb3IgKGxldCBoID0gMDsgaCA8IGZpbHRlckhlaWdodDsgKytoKSB7XG4gICAgICAgICAgICAgIGNvbnN0IGhJbiA9IGhCZWcgKyBoICogZGlsYXRpb25IZWlnaHQ7XG4gICAgICAgICAgICAgIGlmIChoSW4gPj0gMCAmJiBoSW4gPCBpbkhlaWdodCkge1xuICAgICAgICAgICAgICAgIGZvciAobGV0IHcgPSAwOyB3IDwgZmlsdGVyV2lkdGg7ICsrdykge1xuICAgICAgICAgICAgICAgICAgY29uc3Qgd0luID0gd0JlZyArIHcgKiBkaWxhdGlvbldpZHRoO1xuICAgICAgICAgICAgICAgICAgaWYgKHdJbiA+PSAwICYmIHdJbiA8IGluV2lkdGgpIHtcbiAgICAgICAgICAgICAgICAgICAgY29uc3QgdmFsID0gJHhbYl1baEluXVt3SW5dW2RdICsgJGZpbHRlcltoXVt3XVtkXTtcbiAgICAgICAgICAgICAgICAgICAgaWYgKHZhbCA+IGN1clZhbCkge1xuICAgICAgICAgICAgICAgICAgICAgIGN1clZhbCA9IHZhbDtcbiAgICAgICAgICAgICAgICAgICAgICBoSW5NYXggPSBoSW47XG4gICAgICAgICAgICAgICAgICAgICAgd0luTWF4ID0gd0luO1xuICAgICAgICAgICAgICAgICAgICB9XG4gICAgICAgICAgICAgICAgICB9XG4gICAgICAgICAgICAgICAgfVxuICAgICAgICAgICAgICB9XG4gICAgICAgICAgICB9XG4gICAgICAgICAgICBncmFkaWVudHNbYl1baEluTWF4XVt3SW5NYXhdW2RdICs9ICRkeVtiXVtoT3V0XVt3T3V0XVtkXTtcbiAgICAgICAgICB9XG4gICAgICAgIH1cbiAgICAgIH1cbiAgICB9XG5cbiAgICBjb25zdCBkYXRhSWQgPSBjcHVCYWNrZW5kLndyaXRlKFxuICAgICAgICB1dGlsLnRvVHlwZWRBcnJheShncmFkaWVudHMsIHguZHR5cGUpLCB4LnNoYXBlLCB4LmR0eXBlKTtcblxuICAgIHJldHVybiB7ZGF0YUlkLCBzaGFwZTogeC5zaGFwZSwgZHR5cGU6IHguZHR5cGV9O1xuICB9XG59O1xuIl19